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

DOI10.1016/J.DAM.2012.08.006MaRDI QIDQ1759874zbMATH OpenOpenAlexFDO

Authors Santosh N. Kabadi, Abraham P. Punnen

Publication date 22 November 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.08.006

zbMATH Keywords

approximation algorithmscactus extensioncomputational complexityedge-costeven spanning treemaximum cactus extension problemminimum spanning cactus problemodd spanning treespanning cactus

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Review text

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)].

Recommendations

• Spanning cactus: complexity and extensions
• An optimal algorithm to find maximum and minimum height spanning trees on cactus graphs
• scientific article; zbMATH DE number 1330076
• On the distance spread of cacti and bicyclic graphs
• On the vertex separation of cactus graphs
• The maximum weight spanning star forest problem on cactus graphs
• Optimal covering of cacti by vertex-disjoint paths
• On the p-domination number of cactus graphs
• Spanning trees of extended graphs
• Spanning distribution trees of graphs (extended abstract)

Cited in

(7)

• Spanning trees in a cactus
• Two-cacti with minimum number of spanning trees
• A polynomial algorithm for finding \(T\)-span of generalized cacti
• Approximate spanning cactus
• Spanning cactus: complexity and extensions
• Finding cactus roots in polynomial time
• Spanning cactus and spanning cactus extension of outerplanar graphs

This page was built for publication: Spanning cactus of a graph: Existence, extension, optimization, and approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759874)