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

A cactus is an undirected, connected graph in which each edge is contained in exactly one cycle. Equivalently, a cactus is a connected graph in which each block (maximal \(2\)-connected subgraph) is a cycle. The authors address the spanning cactus existence problem (SCEP) which asks if a given graph contains a spanning cactus, the optimization version of the SCEP, the minimum spanning cactus problem (MSCP), which asks for a spanning cactus \(H\) of minimum cost \(\sum_{e\in E(H)} c_e\) in a given graph \(G\) with non-negative edge-costs \(c_e\), \(e\in E(G)\), and the minimum cactus extension problem (MCEP) which, given a graph \(G\) and a partial cactus (a spanning subgraph in which each edge is contained in at most one cycle), asks for an edge set \(S\subseteq E(G)\setminus E(H)\) such that \(H+S\) is a cactus and \(\sum_{e\in S} c_e\) is minimum. Among others, the authors prove that {\parindent=7mm \begin{itemize}\item[(1)]SCEP is NP-complete, and MSCP and MCEP are NP-hard on complete graphs with \(0/1\) edge-costs, \item[(2)]a spanning tree of a complete graph is extendable to a cactus if and only if it has at least one vertex of even degree. \end{itemize}} In general, partial cacti that are cactus-extendable are characterized in Theorem 5, {\parindent=7mm \begin{itemize}\item[(3)] MCEP for spanning trees in complete graphs is solvable in strongly polynomial time. \end{itemize}} The authors also point out that in complete graphs with edge-costs satisfying the triangle inequality, MSCP and the traveling salesman problem are equivalent and have the same approximation hardness. The directed version of MSCP and SCEP were previously discussed by \textit{A. Palbom} [``Complexity of the directed spanning cactus problem,'' Discrete Appl. Math. 146, No. 1, 81--91 (2005; Zbl 1087.90081)].