Complexity of the directed spanning cactus problem
2005 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, Vol. 146, no 1, 81-91 p.Article in journal (Refereed) Published
In this paper we study the complexity of finding a spanning cactus in various graphs. First, we show that the task of determining if there is a directed spanning cactus in a general unweighted digraph is NP-complete. The proof is a reduction from ONE-IN-THREE 3SAT. Secondly, we show that finding the minimum spanning cactus in a directed, weighted complete with triangle inequality is polynomial time equivalent to finding the minimum travelling salesman problem (TSP) tour in the same graph and that they have the same hardness in approximation.
Place, publisher, year, edition, pages
2005. Vol. 146, no 1, 81-91 p.
directed cacti, spanning cacti, complexity, NP-complete, asymmetric TSP
IdentifiersURN: urn:nbn:se:kth:diva-38029DOI: 10.1016/j.dam.2004.08.006ISI: 000226524500007ScopusID: 2-s2.0-12444318575OAI: oai:DiVA.org:kth-38029DiVA: diva2:435920
QC 201108222011-08-222011-08-192011-08-22Bibliographically approved