Exact Algorithms for Edge Deletion to Cactus
arXiv:2603.2765523.3h-index: 1
AI Analysis
For researchers in graph algorithms, this work provides faster exact solutions for a known NP-hard problem and a new polynomial-time result for a related problem.
The paper presents improved exact algorithms for the NP-hard Edge Deletion to Cactus problem and a polynomial-time algorithm for the Spanning Tree to Cactus problem.
We study two related problems on simple, un-directed graphs: Edge Deletion to Cactus and Spanning Tree to Cactus. Edge Deletion to Cactus has been known to be NP-hard on general graphs at least since 1988. We show improved exact algorithms for the former and a polynomial time algorithm for the latter.