Odd Cycle Transversal on P5-free Graphs in Quasi-polynomial Time

An independent set in a graph G is a set of pairwise non-adjacent vertices. A graph G is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycle Transversal problem, the input is a graph G along with a weight function w associating a rational weight with each vertex, and the task is to find a smallest weight vertex subset S in G such that G — S is bipartite; the weight of . We show that Odd Cycle Transversal admits an algorithm with running time on graphs excluding P5 (a path on five vertices) as an induced subgraph. The problem was previously known to be polynomial time solvable on P4-free graphs and NP-hard on P6-free graphs [Dabrowski, Feghali, Johnson, Paesani, Paulusma and Rzążewski, Algorithmica 2020]. Bonamy, Dabrowski, Feghali, Johnson and Paulusma [Algorithmica 2019] posed the existence of a polynomial time algorithm on P5-free graphs as an open problem, this was later re-stated by Rzążewski [Dagstuhl Reports, 9(6): 2019] and by Chudnovsky, King, Pilipczuk, Rzążewski, and Spirkl [SIDMA 2021], who gave an algorithm with running time . While our time algorithm falls short of completely resolving the complexity status of Odd Cycle Transversal on P5-free graphs it shows that the problem is not NP-hard unless every problem in NP is solvable in quasi-polynomial time.