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

作者：Kabadi Santosh N; Punnen Abraham P^*

来源：Discrete Applied Mathematics, 2013, 161(1-2): 167-175.

DOI：10.1016/j.dam.2012.08.006

• Spanning cactus
• Computational complexity
• Approximation algorithms
• Cactus extension
• Odd spanning tree
• Even spanning tree

We show that testing if an undirected graph contains a bridgeless spanning cactus is NP-hard. As a consequence, the minimum spanning cactus problem (MSCP) on an undirected graph with 0-1 edge weights is NP-hard. For any subgraph S of K-n, we give polynomially testable necessary and sufficient conditions for S to be extendable to a cactus in K-n and the weighted version of this problem is shown to be NP-hard. A spanning tree is shown to be extendable to a cactus in K-n if and only if it has at least one node of even degree. When S is a spanning tree, we show that the weighted version can also be solved in polynomial time. Further, we give an O(n(3)) algorithm for computing a minimum cost spanning tree with at least one vertex of even degree on a graph on n nodes. Finally, we show that for a complete graph with edge-costs satisfying the triangle inequality, the MSCP is equivalent to a general class of optimization problems that properly includes the traveling salesman problem and they all have the same approximation hardness.

• 出版日期2013-1