Minimum k-cut
Encyclopedia
In mathematics, the minimum k-cut, is a combinatorial optimization
problem that requires finding a set of edges whose removal would partition the graph to k connected components. These edges are referred to as k-cut. The goal is to find the minimum-weight k-cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing
.
For a fixed k, the problem is polynomial time solvable in O(|V|k2). However, the problem is NP-complete
if k is part of the input. It is also NP-complete if we specify
vertices and ask for the minimum 
-cut which separates these vertices among each of the sets.
that achieves this approximation factor computes a minimum cut
in each connected components and removes the lightest one. This algorithm requires a total of n − 1 max flow computations. Another algorithm achieving the same guarantee uses the Gomory–Hu tree
representation of minimum cuts. Constructing the Gomory–Hu tree requires n − 1 max flow computations, but the algorithm requires an overall O(kn) max flow computations. Yet, it is easier to analyze the approximation factor of the second algorithm.
If we restrict the graph to a metric space, meaning a complete graph
that satisfies the triangle inequality
, and enforce that the output partitions are each of pre-specified sizes, the problem is approximable to within a factor of 3 for any fixed k.
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
problem that requires finding a set of edges whose removal would partition the graph to k connected components. These edges are referred to as k-cut. The goal is to find the minimum-weight k-cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
.
Formal definition
Given an undirected graph G = (V, E) with an assignment of weights to the edges w: E → N and an integer k ∈ {2, 3, …, |V|}, partition V into k disjoint sets F = {C1, C2, …, Ck} while minimizing
For a fixed k, the problem is polynomial time solvable in O(|V|k2). However, the problem is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
if k is part of the input. It is also NP-complete if we specify
vertices and ask for the minimum -cut which separates these vertices among each of the sets.Approximations
Several approximation algorithms exist with an approximation of 2 − 2/k. A simple greedy algorithmGreedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
that achieves this approximation factor computes a minimum cut
Minimum cut
In graph theory, a minimum cut of a graph is a cut whose cutset has the smallest number of elements or smallest sum of weights possible...
in each connected components and removes the lightest one. This algorithm requires a total of n − 1 max flow computations. Another algorithm achieving the same guarantee uses the Gomory–Hu tree
Gomory–Hu tree
In combinatorial optimization, the Gomory–Hu tree of an undirected graph with capacities is a weighted tree that consists of edges representing all pairs minimum s-t cut in the graph...
representation of minimum cuts. Constructing the Gomory–Hu tree requires n − 1 max flow computations, but the algorithm requires an overall O(kn) max flow computations. Yet, it is easier to analyze the approximation factor of the second algorithm.
If we restrict the graph to a metric space, meaning a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
that satisfies the triangle inequality
Triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side ....
, and enforce that the output partitions are each of pre-specified sizes, the problem is approximable to within a factor of 3 for any fixed k.