Spanning cactus of a graph: Existence, extension, optimization, and approximation

We show that testing if an undirected graph contains a bridgeless spanning cactus is NP-hard. As a consequence, the minimum spanning cactus problem (MSCP) on an undirected graph with 0–1 edge weights is NP-hard. For any subgraph SS of KnKn, we give polynomially testable necessary and sufficient conditions for SS to be extendable to a cactus in KnKn and the weighted version of this problem is shown to be NP-hard. A spanning tree is shown to be extendable to a cactus in KnKn if and only if it has at least one node of even degree. When SS is a spanning tree, we show that the weighted version can also be solved in polynomial time. Further, we give an O(n3)O(n3) algorithm for computing a minimum cost spanning tree with at least one vertex of even degree on a graph on nn nodes. Finally, we show that for a complete graph with edge-costs satisfying the triangle inequality, the MSCP is equivalent to a general class of optimization problems that properly includes the traveling salesman problem and they all have the same approximation hardness.