The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz · 2026

Read The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching by Jan Dreier, Nikolas Mählmann, Sebastian Siebertz (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-07606.txt.

Description

A classic theorem says large twin-free graphs must contain a large matching, co-matching, or half-graph as a semi-induced subgraph. Those three patterns define eight graph classes by which indices stay bounded. Jan Dreier and two co-authors completely classify the parameterized complexity of Independent Set, Clique, and Dominating Set across all eight classes.

Drawing tractability and hardness results from the literature and filling the remaining gaps, they show Independent Set is fixed-parameter tractable whenever the half-graph and co-matching indices are bounded. They also construct classes that separate other cases. Parameterized complexity teams get a finished map for three canonical problems across a natural family of graph classes.

Catalog record

CREATORJan Dreier, Nikolas Mählmann, Sebastian Siebertz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-07606

Browse the full library · About the Tower of Babel