Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911691157012480 |
|---|---|
| author | Chudnovsky, Maria Czyżewska, Jadwiga Kluk, Kacper Pilipczuk, Marcin Rzążewski, Paweł |
| author_facet | Chudnovsky, Maria Czyżewska, Jadwiga Kluk, Kacper Pilipczuk, Marcin Rzążewski, Paweł |
| contents | Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph, that satisfies some property definable in CMSO$_2$ logic.
It is believed that each problem expressible with this formalism can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph.
This belief is supported by the existence of a quasipolynomial-time algorithm by Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rzążewski [STOC 2021], and a recent polynomial-time algorithm for $P_6$-free graphs by Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rzążewski [SODA 2024].
In this work we extend polynomial-time tractability of all such problems to $P_7$-free graphs of bounded clique number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_14836 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sparse induced subgraphs in $P_7$-free graphs of bounded clique number Chudnovsky, Maria Czyżewska, Jadwiga Kluk, Kacper Pilipczuk, Marcin Rzążewski, Paweł Data Structures and Algorithms Combinatorics Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph, that satisfies some property definable in CMSO$_2$ logic. It is believed that each problem expressible with this formalism can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph. This belief is supported by the existence of a quasipolynomial-time algorithm by Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rzążewski [STOC 2021], and a recent polynomial-time algorithm for $P_6$-free graphs by Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rzążewski [SODA 2024]. In this work we extend polynomial-time tractability of all such problems to $P_7$-free graphs of bounded clique number. |
| title | Sparse induced subgraphs in $P_7$-free graphs of bounded clique number |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2412.14836 |