Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915960848384000 |
|---|---|
| author | Bieliński, Paweł Rafał Piecyk, Marta Rzążewski, Paweł |
| author_facet | Bieliński, Paweł Rafał Piecyk, Marta Rzążewski, Paweł |
| contents | The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory.
Recently, there has been a growing interest in the complexity of such problems in ordered graphs, i.e., graphs with a fixed linear ordering of vertices.
Such an approach allows us to investigate the boundary of tractability more closely.
However, most results so far concern coloring problems.
In this paper, we focus on the complexity of the Maximum Weight Independent Set (MWIS) problem in classes of ordered graphs.
For every ordered graph $H$, we classify the complexity of MWIS in ordered graphs that exclude $H$ as an induced subgraph into one of the following cases:
(1) solvable in polynomial time,
(2) solvable in quasipolynomial time,
(3) solvable in subexponential time,
(4) NP-hard.
Notably, case (3) contains only one well-structured family of $H$ obtained from two nested edges by adding isolated vertices in a specific way.
Thus, our results yield an almost complete complexity dichotomy for MWIS in classes of ordered graphs defined by a single forbidden induced subgraph into cases solvable in quasipolynomial time and those that are NP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_24343 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs Bieliński, Paweł Rafał Piecyk, Marta Rzążewski, Paweł Data Structures and Algorithms The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, there has been a growing interest in the complexity of such problems in ordered graphs, i.e., graphs with a fixed linear ordering of vertices. Such an approach allows us to investigate the boundary of tractability more closely. However, most results so far concern coloring problems. In this paper, we focus on the complexity of the Maximum Weight Independent Set (MWIS) problem in classes of ordered graphs. For every ordered graph $H$, we classify the complexity of MWIS in ordered graphs that exclude $H$ as an induced subgraph into one of the following cases: (1) solvable in polynomial time, (2) solvable in quasipolynomial time, (3) solvable in subexponential time, (4) NP-hard. Notably, case (3) contains only one well-structured family of $H$ obtained from two nested edges by adding isolated vertices in a specific way. Thus, our results yield an almost complete complexity dichotomy for MWIS in classes of ordered graphs defined by a single forbidden induced subgraph into cases solvable in quasipolynomial time and those that are NP-hard. |
| title | Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.24343 |