Welcome to MathOverflow

Question

3

Is there any remotely efficient way to determine whether a graph can be disconnected by the removal of fewer than k edges, or even one that has a lower asymptotic complexity than just trying each set of k-1 edges?

If it helps, you can assume the graph is k-regular that k is much smaller than the number of vertices.

flag	asked Jul 4 2010 at 8:28 Ricky Demer 6,361●8●31

There is a really nice algorithm due to Nagamochi and Ibaraki which does not use flows, and is easy to implement. I could not quickly find a nice description online, but the paper is: Computing Edge-Connectivity in Multigraphs and Capacitated Graphs SIAM J. Discrete Math. Volume 5, Issue 1, pp. 54-66 (February 1992) – Chris Godsil Jul 4 2010 at 15:48

Joseph Malkevitch · Accepted Answer · 2010-07-04 12:12:15Z UTC

2

Try:

http://portal.acm.org/citation.cfm?id=122416

and the references there.

answered Jul 4 2010 at 12:12

Joseph Malkevitch
1,165●5●5

Joseph O'Rourke · Answer 2 · 2010-07-04 11:15:56Z UTC

5

Generally $k$-connectivity is computed using max-flow min-cut algorithms. I cannot quote you complexities off the top of my head, but you should be able to find the number of edges that disconnect any pair of nodes $(x,y)$, and then iterate over all $O(n^2)$ pairs. A key result here that underpins these algorithms is Menger's Theorem.

answered Jul 4 2010 at 11:15

Joseph O'Rourke
43.1k●1●49●214

2

If G is undirected, you can do better than finding max-flow min-cut over all pairs of vertices. Since you are guaranteed that any given vertex $s$ is contained in one of the partitions of a minimum cut, you can choose any arbitrary vertex $s$ and compute the max flow/min cut to each other vertex $t$. The minimum of these values is the min cut of the graph with cardinality $lambda(G)$, the edge connectivity of G. – Justin Melvin Jul 4 2010 at 14:01

determining k-edge-connectivity of a graph

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.