{"id":"arxiv/2609.30900","url":"https://arxiv.org/abs/2609.30900","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Odd Cycle Transversal on $H$-free graphs","domain":"cs.DS","source":"arxiv","authors":["Esther Galby","Paloma T. de Lima","Andrea Munaro","Amir Nikabadi"],"reviews":0,"subject":"cs.DS","summary":"\\textsc{Odd Cycle Transversal} is a classic $\\mathsf{NP}$-hard graph optimization problem asking for a minimum-weight set of vertices whose deletion makes the input graph bipartite, or equivalently, a maximum-weight induced bipartite subgraph. We show that \\textsc{Odd Cycle Transversal} is quasi-polynomial-time solvable on $kP_4$-free graphs, for every fixed $k \\in \\mathbb{N}$. In fact, we provide an $n^{O_k(\\log n)}$-time algorithm for the more general \\textsc{Max-Weight List $2$-Colorable Induced Subgraph}, where the notation $O_{k}(\\cdot)$ hides factors depending on $k$. Paired with known…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{}}