efficient algorithm for min cut with specified number of vertices

Question

Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to minimize the number of edges going between $C$ and $\bar{C}$. Algorithms are known for this problem which solve it in polynomial time. My question is, what if one additionally specifies the constraint that $|C| = n$ for some $n < |V|$? That is, we wish to find the set of $n$ vertices with the minimal number of edges connecting it to the rest of the vertices. Are there also efficient algorithms for this case? I am interested both in the question of whether this problem is formally solvable in polynomial time (which I would guess that it is) and also in what algorithms are best in practice.

Answer 1

For $n= \frac {|V|} 2$, it's called Minimum Bisection, and it's NP-hard. There exists an $O(\log^{3/2} n)$-approximation: "A polylogarithmic approximation of the minimum bisection".

If you are interested, the more general problem is splitting into multiple components of the same size, and it is called Balanced Graph Partitioning. For more than 2 parts no finite approximation exists unless P=NP: "Balanced Graph Partitioning" (Andreev, Rakke), since you can't efficiently check if the answer is 0.

If the parts are not necessarily exactly balanced (a small imbalance is allowed), an $O(\log n)$-approximation algorithm exists: "Balanced Partitions of Trees and Applications".

---

Some algorithms (also check https://en.wikipedia.org/wiki/Graph_partition and "references" sections of the following papers):

• Local search with various flavors: we start with some partitioning and then try to swap vertices between parts to minimize the cut. E.g. we compute "gain" for each vertex (improvement if we move it to another part), and swap vertices with the maximum gain. Its advantage is that you can apply it after any other algorithm.

• Spectral partitioning (see e.g. Spectral Graph Theory and Graph Partitioning): uses the second eigenvector of a Laplacian matrix to approximate the partitioning (e.g. by moving the smallest $|V|/2$ coordinates to the first part). Works surprisingly well. However, I'm not sure it can be adapted to the case when you want an unbalanced bisection (e.g. $1:2$ instead of $1:1$).

• Linear embedding: "Distributed Balanced Partitioning via Linear Embedding". We embed vertices into a one-dimensional array while minimizing sum over all pairs of vertices: the distance between them multiplied by the weight of their edge. Then we just split this array into consecutive chunks of required sizes. Didn't work that well in my experience.

• (Ads) Our paper: "Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent", where we used gradient descent to find minimum bisection: for each vertex we introduce a variable which roughly represents a probability that the vertex belongs to the first part, and minimizing the cut reduces to constrained optimization of a quadratic function. It's a bit outperformed in practice by a fine-tuned local search, but it works really well when you have multiple balance constraints.

Aside from the spectral method, all of them can be trivially adapted to partitioning the graph in arbitrary proportions.

There are also standard solvers: KaHIP, METIS. In my experience, KaHIP was pretty good. I'm not sure they support splitting into parts of arbitrary sizes though.