So you want to evaluate the polynomial $$ p(x) = \sum_{C} x^{|C|} $$ where $C$ ranges over all nearly-minimum cuts in a graph (say, all minimal cuts of size $\alpha c$ where $c$ is the edge connectivity.) Here $\alpha$ is a small constant $>1$.

You can do any precomputation you want.

Two obvious algorithms present themselves. This is a polynomial of degree at most $\alpha c$, so you can do this is $O(c)$. Alternatively, for $\alpha$ sufficiently close to 1, the number of such cuts is at most $O(n^2)$, so you can do this in $O(n^2)$ work.

Are there any other algorithms available?

For $\alpha$ sufficiently close to 1, the set of all such cuts has a very nice structure, and these cuts can be represented in $O(n)$ space.


Your Answer

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

Browse other questions tagged or ask your own question.