-д хадгалсан:
| Үндсэн зохиолчид: | , |
|---|---|
| Формат: | Preprint |
| Хэвлэсэн: |
2024
|
| Нөхцлүүд: | |
| Онлайн хандалт: | https://arxiv.org/abs/2402.08046 |
| Шошгууд: |
Шошго нэмэх
Шошго байхгүй, Энэхүү баримтыг шошголох эхний хүн болох!
|
Агуулга:
- 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.