4
$\begingroup$

I have been studying for my algorithms exam and whilst doing previous exams found this question for which I am not sure how to handle.

Given a graph $G=(V,E)$ with integer capacities $C:E \rightarrow \mathbb{N}$, find an efficient algorithm to determine whether the graph has a min cut of at most $k$ edges (assume $k=100$).

My thinking was computing a min cut, then for every edge on that cut, increase it by 1 and compute the min cut again - if the max flow has risen, that means that that edge exists in every single min cut. And If I found there to be over 100 of these edges, then there is no min cut of at most $k$ edges.

However, I don't think that if I found there to be less 100 of these edges, there's necessarily a min cut of at most 100 edges.

$\endgroup$

1 Answer 1

2
$\begingroup$

Apply the transformation $w \mapsto (m+1)w + 1$ to all weights (where $m$ is the number of edges in the graph), and find the minimum weight cut in the new graph. This will give you the minimum weight cut with the minimum number of edges. By computing the value modulo $m+1$, you can determine the number of edges.

$\endgroup$
7
  • $\begingroup$ Hello, thank you for your response. By m, do you mean the value of the max flow? $\endgroup$ Jul 1, 2019 at 19:49
  • $\begingroup$ Oops... it should be the number of edges. $\endgroup$ Jul 1, 2019 at 19:51
  • $\begingroup$ I am still slightly confused, do you mean m is the number of edges in the graph in general, or the desired number of edges in the mincut? Also sadly I am not sure I follow why this transformation gives me a min cut with a minimum number of edges $\endgroup$ Jul 1, 2019 at 19:56
  • $\begingroup$ Number of edges in the graph. $\endgroup$ Jul 1, 2019 at 19:57
  • $\begingroup$ I think i get it, I just have one quick question. Why do we have to multiply by m+1? Is it because the transformation wouldn't preserve the mincut (i.e wouldn't find a mincut that is also a mincut of the original graph) otherwise? If so, why is that? $\endgroup$ Jul 1, 2019 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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