Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.00265 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917076944289792 |
|---|---|
| author | Chudnovsky, Maria Hajebi, Sepehr Lokshtanov, Daniel Spirkl, Sophie |
| author_facet | Chudnovsky, Maria Hajebi, Sepehr Lokshtanov, Daniel Spirkl, Sophie |
| contents | A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is 3PC-free if no induced subgraph of it is a three-path-configuration. We prove that 3PC-free graphs have poly-logarithmic tree-independence number. More explicitly, we show that there exists a constant $c$ such that every $n$-vertex 3PC-free graph graph has a tree decomposition in which every bag has stability number at most $c (\log n)^2$. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems, that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is 3PC-free. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_00265 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tree independence number II. Three-path-configurations Chudnovsky, Maria Hajebi, Sepehr Lokshtanov, Daniel Spirkl, Sophie Combinatorics A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is 3PC-free if no induced subgraph of it is a three-path-configuration. We prove that 3PC-free graphs have poly-logarithmic tree-independence number. More explicitly, we show that there exists a constant $c$ such that every $n$-vertex 3PC-free graph graph has a tree decomposition in which every bag has stability number at most $c (\log n)^2$. This implies that the Maximum Weight Independent Set problem, as well as several other natural algorithmic problems, that are known to be NP-hard in general, can be solved in quasi-polynomial time if the input graph is 3PC-free. |
| title | Tree independence number II. Three-path-configurations |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.00265 |