Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915804207906816 |
|---|---|
| author | Majewski, Konrad Masařík, Tomáš Novotná, Jana Okrasa, Karolina Pilipczuk, Marcin Rzążewski, Paweł Sokołowski, Marek |
| author_facet | Majewski, Konrad Masařík, Tomáš Novotná, Jana Okrasa, Karolina Pilipczuk, Marcin Rzążewski, Paweł Sokołowski, Marek |
| contents | We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw $S_{t,t,t}$ as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time $2^{\mathcal{O}(\sqrt{n}\log n)}$ and a quasipolynomial-time approximation scheme with improved running time $2^{\mathcal{O}(\varepsilon^{-1} \log^{5} n)}$.
The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in $P_t$-free graphs, ensures that given an $n$-vertex $P_t$-free graph, in polynomial time we can find a set $P$ of at most $t-1$ vertices, such that every connected component of $G-N[P]$ has at most $n/2$ vertices. Our main technical contribution is an analog of this result for $S_{t,t,t}$-free graphs: given an $n$-vertex $S_{t,t,t}$-free graph, in polynomial time we can find a set $P$ of $\mathcal{O}(t \log n)$ vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of $G-N[P]$ such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most $n/2$ vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_04836 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument Majewski, Konrad Masařík, Tomáš Novotná, Jana Okrasa, Karolina Pilipczuk, Marcin Rzążewski, Paweł Sokołowski, Marek Data Structures and Algorithms Discrete Mathematics Combinatorics We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw $S_{t,t,t}$ as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time $2^{\mathcal{O}(\sqrt{n}\log n)}$ and a quasipolynomial-time approximation scheme with improved running time $2^{\mathcal{O}(\varepsilon^{-1} \log^{5} n)}$. The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in $P_t$-free graphs, ensures that given an $n$-vertex $P_t$-free graph, in polynomial time we can find a set $P$ of at most $t-1$ vertices, such that every connected component of $G-N[P]$ has at most $n/2$ vertices. Our main technical contribution is an analog of this result for $S_{t,t,t}$-free graphs: given an $n$-vertex $S_{t,t,t}$-free graph, in polynomial time we can find a set $P$ of $\mathcal{O}(t \log n)$ vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of $G-N[P]$ such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most $n/2$ vertices. |
| title | Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2203.04836 |