# Determining the minimum number of edges to add in order to be 3-connected

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.

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.
• If you can go from $k-1$ to $k$ in polynomial time, you can go from $0$ to $k$ by iterating. Since $k$ is bounded by $|V(G)|$, that gives a polynomial-time algorithm. Dec 20 '14 at 14:55