Conference Paper,
Odd Cycle Transversal on P-free Graphs in Quasi-polynomial Time
Affiliations
- [1] Indian Institute of Technology Madras [NORA names: India; Asia, South];
- [2] IT University of Copenhagen [NORA names: ITU IT University of Copenhagen; University; Denmark; Europe, EU; Nordic; OECD];
- [3] Institute of Mathematical Sciences [NORA names: India; Asia, South];
- [4] University of Bergen [NORA names: Norway; Europe, Non-EU; Nordic; OECD];
- [5] Max Planck Institute for Informatics [NORA names: Germany; Europe, EU; OECD]
Abstract
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 S, (equation presented). We show that Odd Cycle Transversal admits an algorithm with running time n 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 (Equation presented). While our (Equation presented) 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.