Spanning cactus of a graph: Existence, extension, optimization, and approximation
type: Item
instance of: scholarly article
title: Spanning cactus of a graph: Existence, extension, optimization, and approximation
zbMATH Open document ID: 1258.05101
author: Santosh N. Kabadi
author: Abraham P. Punnen
published in: Discrete Applied Mathematics
publication date: 2012-11-22T00:00:00Z
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)].
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6109941
zbMATH Keywords: spanning cactus
zbMATH Keywords: computational complexity
zbMATH Keywords: approximation algorithms
zbMATH Keywords: cactus extension
zbMATH Keywords: odd spanning tree
zbMATH Keywords: even spanning tree
zbMATH Keywords: minimum spanning cactus problem
zbMATH Keywords: maximum cactus extension problem
zbMATH Keywords: edge-cost
MaRDI profile type: Publication
full work available at URL: j.dam.2012.08.006
OpenAlex ID: W2085596541
DOI: 10.1016/J.DAM.2012.08.006
Recommended article: Spanning cactus: complexity and extensions
Recommended article: Q3539528
Recommended article: Q4258252
Recommended article: On the distance spread of cacti and bicyclic graphs
Recommended article: Q3514059
Recommended article: The maximum weight spanning star forest problem on cactus graphs
Recommended article: Optimal covering of cacti by vertex-disjoint paths
Recommended article: On the p-domination number of cactus graphs
Recommended article: Spanning trees of extended graphs
Recommended article: Spanning Distribution Trees of Graphs
description: scientific article; zbMATH DE number 6109941