Complexity of the directed spanning cactus problem Original Research Article

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 graph 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.