版本更新 · v2arXiv:2603.27655
Exact Algorithms for Edge Deletion to Cactus
Sheikh Shakil Akhtar, Geevarghese Philip
原文摘要
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.
cs.DS · cs.CC · cs.DM · math.CO