Consider an undirected graph with a source and a sink vertex. We would like to remove minimum number of vertices in that graph to disconnect any path between source and sink.
Can we do this using say a max-flow, min-cut algorithm?
$\begingroup$
$\endgroup$
2
-
4$\begingroup$ It should work (I assume all edges have the same capacity). $\endgroup$– A.SchulzDec 17, 2012 at 9:26
-
1$\begingroup$ Check this question on CSTheory $\endgroup$– adrianNSep 4, 2014 at 12:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
(This answer was originally given as part of the question, with the goal of it being verified.)
My intuition tells me that we can use max-flow, min-cut algorithm to solve this problem:
- Replace each of the undirected edges with a pair of directed edges.
- Replace each vertex $v$ with two vertices $v_\text{in}$ and $v_\text{out}$ connected by an edge. all the incoming edges of $v$ will be connected with $v_\text{in}$, all the outgoing edges of $v$ will be connected with $v_\text{out}$.
- Try to find a minimum cut $M$. The edges of $M$ refer to the vertices that we need to remove.
-
$\begingroup$ It's not clear to me why this would be guaranteed towork. What if the minimum cut of the modified graph includes some edges that are not between some $v_\text{in}$ and $v_\text{out}$, but are a directed edge from step 1 of the solution? Why do you think that each min-vertex-cut of the original graph will be in one-to-one correspondence with a min-edge-cut of the modified graph? I think a proof is needed. $\endgroup$– D.W. ♦Sep 5, 2014 at 6:02
-
$\begingroup$ To support the answer by FrankW, please follow the below links, there is a paper from Abdol–Hossein Esfahanian supporting the replacement of an undirected edge with two directed edges. - networkx.github.io/documentation/latest/reference/generated/… - cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf $\endgroup$– PawanOct 28, 2015 at 23:53
-
2$\begingroup$ @pawanp, I don't follow you. Of course you can replace an undirected edge with two directed edges. The question is not whether you can do it, but whether after applying the algorithm FrankW listed, whether the output is guaranteed to be a correct solution to the original problem. I don't see how NetworkX library man page is relevant. Regarding the paper: it's 14 pages long, with 11 different algorithms, most with no proof of correctness. Can you be more specific about exactly which part you see as relevant here? $\endgroup$– D.W. ♦Oct 29, 2015 at 23:46