[Solved]: Determining the minimum number of edges to add in order to be 3-connected

Problem Detail: 

A graph $G$ is said to be $3$-connected if it has no $2$-vertex cutsets (i.e., at least three vertices must be deleted to disconnect the graph). As far as I know, it is possible to determine if a simple graph is $3$-connected in $O(n)$ time (example: http://www2.tu-ilmenau.de/combinatorial-optimization/Schmidt2012b.pdf), but I would find it useful to efficiently determine which edges to add in order to make our graph $3$-connected if it isn't already (ideally, the minimum number of edges if this can be done efficiently). Is anyone aware of such an algorithm? If so, I would appreciate a reference or two.

Asked By : user340082710

Answered By : Chao Xu

For this special case of $3$-connectivity, it has been solved by Watanabe and Nakamura. The algorithm runs in $O(n(n+m)^2)$ time, where $n$ and $m$ are the number of vertices and edges of the input graph, respectively.

There is a polynomial time algorithm to find the minimum number of edges to add to a $k-1$-connected graph to produce a $k$-connected graph. See chapter 3 of László A. Végh's PhD thesis. The thesis states that it is not known if adding a minimum number of edges to produce a $k$-connected graph is NP-hard in general.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35484

3.2K people like this

 Download Related Notes/Documents