Prof. Akanksha Agarwal
Prof. Akanksha Agarwal
Polynomial Time Algorithm For Odd Cycle Transversal on P_5-free Graphs
Abstract: Several classical NP-hard graph problems become tractable if we restrict ourselves to structured graphs. In this talk our focus will be to obtain a polynomial time algorithm for one such problem in a structured graph class. A vertex subset in a graph is an independent set if no pair of vertices in the set have an edge between them. A graph is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycle Transversal problem, we are given a graph G and a rational vertex weight function w:V(G) -> Q, and the task is to find a smallest weight vertex subset S in G such that G-S is bipartite; the weight of S, w(S) is the sum of weights of vertices in S. For an integer i, a graph is Pi-free if it does not contain a path on i vertices as an induced subgraph. By result of Dabrowski et al., Odd Cycle Transversal is polynomial time solvable on P_4-free graphs and it is NP-hard on P6-free graphs. We will close the pesky gap by obtaining a polynomial time algorithm for Odd Cycle Transversal on P_5 free graphs.