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 (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 O^* (12^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 O^* ( (12-) ^lcw) even when parameterized by linear clique-width. This answers the second question posed by Hegerfeld and Kratsch in the same paper.