Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs

Paweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski · 2026

Read Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs by Paweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski (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-2604-24343.txt.

Introduction

Bielinski, Piecyk, and Rzazewski classify maximum weight independent set complexity in ordered graphs with one forbidden induced subgraph. For every ordered graph H, the problem lands in one of four cases: polynomial time, quasipolynomial time, subexponential time, or NP-hard. Only one well-structured family, built from two nested edges plus isolated vertices added in a specific way, falls in the subexponential case. The result is an almost complete dichotomy: classes solvable in quasipolynomial time versus those that are NP-hard.

Catalog record

CREATORPaweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE379370
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel