Metraipolis › archive › dc_214813872d40

Odd Cycle Transversal on $H$-free graphs — arXiv:2609.30900

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.30900
License (as archived)
CC0-1.0
Archived
2026-10-08T02:59:23.808Z
SHA-256 of the archived text
b42b0734300313ca88e1d6042db56c23b916bb38ee9bda34c0bac06a336c6fc4
Stable URL of this page
https://metraipolis.com/documento/dc_214813872d40

How to cite

Odd Cycle Transversal on $H$-free graphs — arXiv:2609.30900 — arXiv (en), https://arxiv.org/abs/2609.30900 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_214813872d40 (Metraipolis archive dc_214813872d40, sha256 b42b0734300313ca88e1d6042db56c23b916bb38ee9bda34c0bac06a336c6fc4)
BibTeX
@misc{dc214813872d40,
  title = {Odd Cycle Transversal on $H$-free graphs — arXiv:2609.30900},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.30900},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_214813872d40; sha256 b42b0734300313ca88e1d6042db56c23b916bb38ee9bda34c0bac06a336c6fc4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.30900. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

\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 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 $\mathsf{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\ge2$, 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\ge2$, 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].

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in math.CO).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.30900 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T02:28:17.948Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).