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.

  • 3
    $\begingroup$ 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. $\endgroup$ – David Richerby Dec 20 '14 at 14:55
  • $\begingroup$ I updated the answer after a more careful reading of the thesis. $\endgroup$ – Chao Xu Dec 21 '14 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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