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
| CREATOR | Jan Dreier, Nikolas Mählmann, Sebastian Siebertz |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 57 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-07606