2026-07-20T05:27:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25151 2026-02-09T08:17:54Z ddc:004 open_access

Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width Bojikian, Narek Kratsch, Stefan Parameterized complexity connected odd cycle transversal clique-width Recently, Bojikian and Kratsch [ICALP 2024] presented a novel approach to tackle connectivity problems parameterized by clique-width (cw), based on counting (modulo 2) the number of representations of partial solutions, while allowing for possibly multiple representations to exist for the same partial solution. Using this technique, they got a SETH-tight bound of 𝒪^*(3^{cw}) for the Steiner Tree problem, which was left open by Hegerfeld and Kratsch [ESA 2023]. We use the same technique to solve the Connected Odd Cycle Transversal problem in time 𝒪^*(12^{cw}). Moreover, we prove that our result is tight by providing a SETH-based lower bound excluding algorithms with running time 𝒪^*((12-ε)^{cw}). This answers another question of Hegerfeld and Kratsch [ESA 2023]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Narek Bojikian and Stefan Kratsch 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.19 urn:nbn:de:0030-drops-251516 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.19 eng https://creativecommons.org/licenses/by/4.0/legalcode