Exact Algorithms for Edge Deletion to Cactus
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908919507451904 |
|---|---|
| author | Akhtar, Sheikh Shakil Philip, Geevarghese |
| author_facet | Akhtar, Sheikh Shakil Philip, Geevarghese |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_27655 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exact Algorithms for Edge Deletion to Cactus Akhtar, Sheikh Shakil Philip, Geevarghese Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics 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. |
| title | Exact Algorithms for Edge Deletion to Cactus |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2603.27655 |