Clique-Width: Harnessing the Power of Atoms
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914337000521728 |
|---|---|
| author | Dabrowski, Konrad K. Masařík, Tomáš Novotná, Jana Paulusma, Daniël Rzążewski, Paweł |
| author_facet | Dabrowski, Konrad K. Masařík, Tomáš Novotná, Jana Paulusma, Daniël Rzążewski, Paweł |
| contents | Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph class ${\cal G}$ if they are so on the atoms (graphs with no clique cut-set) of ${\cal G}$. Hence, we initiate a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A graph $G$ is $H$-free if $H$ is not an induced subgraph of $G$, and it is $(H_1,H_2)$-free if it is both $H_1$-free and $H_2$-free. A class of $H$-free graphs has bounded clique-width if and only if its atoms have this property. This is no longer true for $(H_1,H_2)$-free graphs, as evidenced by one known example. We prove the existence of another such pair $(H_1,H_2)$ and classify the boundedness of clique-width on $(H_1,H_2)$-free atoms for all but 18 cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_03578 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Clique-Width: Harnessing the Power of Atoms Dabrowski, Konrad K. Masařík, Tomáš Novotná, Jana Paulusma, Daniël Rzążewski, Paweł Discrete Mathematics Computational Complexity Combinatorics 05C75 Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph class ${\cal G}$ if they are so on the atoms (graphs with no clique cut-set) of ${\cal G}$. Hence, we initiate a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A graph $G$ is $H$-free if $H$ is not an induced subgraph of $G$, and it is $(H_1,H_2)$-free if it is both $H_1$-free and $H_2$-free. A class of $H$-free graphs has bounded clique-width if and only if its atoms have this property. This is no longer true for $(H_1,H_2)$-free graphs, as evidenced by one known example. We prove the existence of another such pair $(H_1,H_2)$ and classify the boundedness of clique-width on $(H_1,H_2)$-free atoms for all but 18 cases. |
| title | Clique-Width: Harnessing the Power of Atoms |
| topic | Discrete Mathematics Computational Complexity Combinatorics 05C75 |
| url | https://arxiv.org/abs/2006.03578 |