Odd Cycle Transversal in $P_k$-Free Graphs
2026-06-05 • Data Structures and Algorithms
Data Structures and AlgorithmsDiscrete Mathematics
AI summaryⓘ
The authors study a graph problem called Odd Cycle Transversal (OCT), which involves removing the smallest number of vertices to make a graph bipartite (no odd cycles). While this problem is generally very hard, especially in certain restricted graphs called Pk-free graphs, the authors identify special cases where it can be solved efficiently. They use these cases to create an approximation algorithm that finds a near-optimal solution for OCT in Pk-free graphs, with a guaranteed accuracy depending on k. Their work bridges gaps between known hardness results and tractable approximations for these graphs.
Odd Cycle TransversalBipartite GraphPk-free GraphsApproximation AlgorithmNP-completeUnique Games ConjecturePolynomial-timeGraph DecompositionComputational Complexity
Authors
Akramah Faizi, Arash Rafiey
Abstract
The Odd Cycle Transversal (OCT) problem, which asks for a minimum subset of vertices whose removal renders a graph bipartite, is a central problem in algorithmic graph theory. It is known to be NP-complete even on $P_k$-free graphs for $k \ge 6$. Furthermore, assuming the Unique Games Conjecture (UGC), OCT does not admit a constant-factor approximation algorithm on general graphs. Motivated by these hardness results, we investigate the approximability of OCT on $P_k$-free graphs. We first establish that the problem becomes polynomial-time solvable on specific subclasses of $P_k$-free graphs, most notably $(P_6, C_3)$-free graphs, by exploiting a structural decomposition into rings of bipartite graphs. Leveraging these tractable substructures as a basis, we present a constant-factor approximation algorithm for OCT on general $P_k$-free graphs. We achieve an approximation ratio of $k-2$ when $k$ is odd and $k-3$ when $k$ is even. These results provide the first nontrivial constant-factor approximations for this class dependent on $k$, aligning with the UGC implication that no approximation factor independent of $k$ is likely to exist.