{"id":"arxiv/2603.27655","url":"https://arxiv.org/abs/2603.27655","tags":["cs.DS","cs.CC","cs.DM","math.CO"],"score":0,"title":"Exact Algorithms for Edge Deletion to Cactus","domain":"cs.DS","source":"arxiv","authors":["Sheikh Shakil Akhtar","Geevarghese Philip"],"reviews":0,"subject":"cs.DS","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-29","reactions":{}}