Hardness and Tractability of ๐ฏ h + 1 \mathcal{T}_{h+1} - Free Edge Deletion A preliminary version has been published in the proceedings of the 25th International Symposium on Fundamentals of Computation Theory (FCT) 2025.
Ajinkya Gaikwad, Soumen Maity, Leeja R ยท 2026
Read Hardness and Tractability of ๐ฏ h + 1 \mathcal{T}_{h+1} - Free Edge Deletion A preliminary version has been published in the proceedings of the 25th International Symposium on Fundamentals of Computation Theory (FCT) 2025. by Ajinkya Gaikwad, Soumen Maity, Leeja R (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-00644.txt.
Description
Ajinkya Gaikwad and colleagues study edge deletion for graphs whose connected pieces must all stay small. Deleting at most a given number of edges so every component stays below a given size is NP-complete once that size reaches three. It is easy when the size is at most two. The authors strengthen earlier hardness results under new structural parameters, including distances to disjoint paths and stars and the twin cover number. They also recover tractability under other combinations, give a bicriteria approximation, and settle split, interval, and directed cases.
Catalog record
| CREATOR | Ajinkya Gaikwad, Soumen Maity, Leeja R |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64848 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602.00644