Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
<|reference_start|>Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width: 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-\epsilon)^{\operatorname{lcw}})$ even when parameterized by linear clique-width. This answers the second question posed by Hegerfeld and Kratsch in the same paper.<|reference_end|>
@article{bojikian2024tight,
    title={Tight Algorithm for Connected Odd Cycle Transversal Parameterized by
  Clique-width},
    author={Narek Bojikian, Stefan Kratsch},
    journal={arXiv preprint arXiv:2402.08046},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08046},
    primaryClass={cs.DS}
}