Odd Cycle Transversal on H-free graphs
Abstract
\textsc{Odd Cycle Transversal} is a classic 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 kP4-free graphs, for every fixed k ∈ ℕ. In fact, we provide an nOk(log n)-time algorithm for the more general \textsc{Max-Weight List $2$-Colorable Induced Subgraph}, where the notation Ok(·) hides factors depending on k. Paired with known results from the literature, this allows us to obtain a complete complexity dichotomy for these two problems on H-free graphs into cases solvable in quasi-polynomial time and cases which are NP-hard, in particular resolving an open problem of Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024]. Our algorithms are based on a new structural tool that may be of independent interest. We introduce the notion of H-amiable family and show that, for every fixed graph H without isolated vertices and every fixed k≥2, every kH-free graph admits an H-amiable family of quasi-polynomial size that can be constructed in quasi-polynomial time. Besides yielding the aforementioned algorithms, this result gives, for every fixed connected graph H and every fixed k≥2, a reduction from \textsc{Max-Weight Independent Set} on kH-free graphs to the same problem on H-free graphs with nOH,k(log n) overhead. In this setting, it improves the nOH,k(log3 n) overhead obtained by specializing the general reduction of Gartland and Lokshtanov [FOCS 2020].
Related
- On two problems concerning the geodesic transversal number of graphs
- Additive mappings of unweighted directed graphs preserving individual values of the cycle length
- Maximum index of unbalanced signed graphs without a positive odd cycle
- The sparse regularity method for graphs with few even-cycle homomorphisms
- Extremal graphs with cycle lengths in a fixed residue class
BibTeX
@misc{galby2026cycle,
title = {{Odd Cycle Transversal on $H$-free graphs}},
author = {Esther Galby and Paloma T. de Lima and Andrea Munaro and Amir Nikabadi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30900},
eprint = {2609.30900},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30900},
}
RIS
TY - UNPB
TI - Odd Cycle Transversal on H-free graphs
AU - Esther Galby
AU - Paloma T. de Lima
AU - Andrea Munaro
AU - Amir Nikabadi
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.30900
UR - https://arxiv.org/abs/2609.30900
AB - \textsc{Odd Cycle Transversal} is a classic 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 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(·) hides factors depending on k. Paired with known results from the literature, this allows us to obtain a complete complexity dichotomy for these two problems on H-free graphs into cases solvable in quasi-polynomial time and cases which are NP-hard, in particular resolving an open problem of Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024]. Our algorithms are based on a new structural tool that may be of independent interest. We introduce the notion of H-amiable family and show that, for every fixed graph H without isolated vertices and every fixed k≥2, every kH-free graph admits an H-amiable family of quasi-polynomial size that can be constructed in quasi-polynomial time. Besides yielding the aforementioned algorithms, this result gives, for every fixed connected graph H and every fixed k≥2, a reduction from \textsc{Max-Weight Independent Set} on kH-free graphs to the same problem on H-free graphs with n^O_H,k(log n) overhead. In this setting, it improves the n^O_H,k(log^3 n) overhead obtained by specializing the general reduction of Gartland and Lokshtanov [FOCS 2020].
ER -