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
    0 references
    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
    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

    Identifiers