Defending Planar Graphs against Star-Cutsets

We consider the problem of protecting edges in a graph so that the graph remains connected after the removal of any set of vertices that form a star consisting of unprotected edges. We show that the problem of finding a minimal set of edges to protect (the network protection problem) is NP-complete in general graphs, and present an O(logn)-approximation algorithm, where the O(logn) factor is essentially best possible. Our major focus, though, is on the special case of planar graphs. We analyse in detail the structure of minimal star-cutsets in planar graphs, and exploit this structure to construct a polynomial time approximation scheme for the network protection problem.