Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913243579023360 |
|---|---|
| author | Bojikian, Narek Kratsch, Stefan |
| author_facet | Bojikian, Narek Kratsch, Stefan |
| contents | Recently, Bojikian and Kratsch [2023] have presented a novel approach to tackle connectivity problems parameterized by clique-width ($\operatorname{cw}$), based on counting small representations of partial solutions (modulo two). Using this technique, they were able to get a tight bound for the Steiner Tree problem, answering an open question posed by Hegerfeld and Kratsch [ESA, 2023]. We use the same technique to solve the Connected Odd Cycle Transversal problem in time $\mathcal{O}^*(12^{\operatorname{cw}})$. We define a new representation of partial solutions by separating the connectivity requirement from the 2-colorability requirement of this problem. Moreover, we prove that our result is tight by providing SETH-based lower bound excluding algorithms with running time $\mathcal{O}^*((12-ε)^{\operatorname{lcw}})$ even when parameterized by linear clique-width. This answers the second question posed by Hegerfeld and Kratsch in the same paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08046 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width Bojikian, Narek Kratsch, Stefan Data Structures and Algorithms 05C85 F.2 Recently, Bojikian and Kratsch [2023] have presented a novel approach to tackle connectivity problems parameterized by clique-width ($\operatorname{cw}$), based on counting small representations of partial solutions (modulo two). Using this technique, they were able to get a tight bound for the Steiner Tree problem, answering an open question posed by Hegerfeld and Kratsch [ESA, 2023]. We use the same technique to solve the Connected Odd Cycle Transversal problem in time $\mathcal{O}^*(12^{\operatorname{cw}})$. We define a new representation of partial solutions by separating the connectivity requirement from the 2-colorability requirement of this problem. Moreover, we prove that our result is tight by providing SETH-based lower bound excluding algorithms with running time $\mathcal{O}^*((12-ε)^{\operatorname{lcw}})$ even when parameterized by linear clique-width. This answers the second question posed by Hegerfeld and Kratsch in the same paper. |
| title | Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width |
| topic | Data Structures and Algorithms 05C85 F.2 |
| url | https://arxiv.org/abs/2402.08046 |