Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 '10 at 15:48
add comment

2 Answers

up vote 2 down vote accepted

Try:

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

and the references there.

share|improve this answer
add comment

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.

share|improve this answer
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 '10 at 14:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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