Spanning cactus of a graph: Existence, extension, optimization, and approximation (Q1759874)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Spanning cactus of a graph: Existence, extension, optimization, and approximation |
scientific article |
Statements
Spanning cactus of a graph: Existence, extension, optimization, and approximation (English)
0 references
22 November 2012
0 references
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)].
0 references
spanning cactus
0 references
computational complexity
0 references
approximation algorithms
0 references
cactus extension
0 references
odd spanning tree
0 references
even spanning tree
0 references
minimum spanning cactus problem
0 references
maximum cactus extension problem
0 references
edge-cost
0 references