3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – Chris Godsil
    Commented Jul 4, 2010 at 15:48

2 Answers 2

Reset to default
2
$\begingroup$

Try:

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

and the references there.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Generally vertex connectivity higher than 3 is harder to compute than edge connectivity, so this conversion is not a good idea in practice. $\endgroup$
    – Brendan McKay
    Commented Mar 16 at 6:36
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Justin Melvin
    Commented Jul 4, 2010 at 14:01

You must log in to answer this question.