# What does it mean for an algorithm to be approximable within $\vert V\vert\cdot (k-1)/k$?

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?

## 1 Answer

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$.)