3
$\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
$\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$
  • $\begingroup$ Hello, thank you for your response. By m, do you mean the value of the max flow? $\endgroup$ – Guy Schwartzberg Jul 1 at 19:49
  • $\begingroup$ Oops... it should be the number of edges. $\endgroup$ – Yuval Filmus Jul 1 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$ – Guy Schwartzberg Jul 1 at 19:56
  • $\begingroup$ Number of edges in the graph. $\endgroup$ – Yuval Filmus Jul 1 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$ – Guy Schwartzberg Jul 1 at 20:09

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.