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

CREATORAjinkya Gaikwad, Soumen Maity, Leeja R
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64848
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602.00644

Browse the full library ยท About the Tower of Babel