With the reference to the following problem:

Given an undirected weighted graph $G$ with, say $N=5000$ vertices. Suppose I'd like to obtain a minimum-k-cut with $k=50$.

As far as my understanding goes, the problem should be solvable in $O(5000^{30})$ time. In the reference here it says that

If the sets in the partition are restricted to be of equal size, the problem is approximable within $\vert V\vert\cdot (k-1)/k$?

Suppose the partitions are indeed of equal size (ie 100 vertices per set). What does this statement mean?


If we look at the cited source, the discussion in section 6 indicates that this is the factor by which the result exceeds the value of the minimal $k$-cut.

That is, if the minimum $k$-cut with $k$ equal-size pieces has weight $x$, there is an algorithm guaranteed to find a $k$-cut with $k$ equal-size pieces that has weight at most $|V| \cdot (1 - \frac1k) \cdot x$. For separating $5000$ vertices into $50$ equal-size pieces, that's $4900 \cdot x$.

If you're not interested in adding the requirement that the pieces should be equal, we can do better. If the minimum $k$-cut has weight $y$, the algorithm presented earlier in the same paper is guaranteed to find a $k$-cut with weight at most $(2 - \frac 2k) \cdot y$.

(Also, $O(5000^{30})$ doesn't mean what you want it to mean. And I see no indication that there's an exact algorithm as fast as what you want it to mean; the page you linked to says that there's an $O(|V|^{k^2})$ algorithm, which is $O(|V|^{2500})$ when $k=50$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.