LP Approach to Odd Cycle Transversal in Perfect Graphs

Given an undirected graph G, a subset S of vertices is said to be an odd cycle transversal (OCT) if it has at least one vertex from every odd cycle in G. That is, S is an OCT if G-S is bipartite (2-colorable).

The problem of finding an optimum OCT generalizes the classical VERTEX COVER problem as a vertex cover is a set of vertices whose deletion results in a 1-colorable graph. Both these problems belong to the important class of vertex deletion problems and are known to be NP-hard in general. One of the largest classes of graphs on which VERTEX COVER is known to be polynomial-time solvable is the class of perfect graphs. This classical polynomial-time algorithm, due to Gr{\"o}tschel, Lov{\'a}sz and Schrijver, is based on semi-definite programming and polyhedral combinatorics. Similar polyhedral structure and complexity results do not extend to OCT, which remains NP-hard on perfect graphs.

We introduce a linear programming formulation for OCT that generalizes the formulation known for VERTEX COVER based on clique constraints. Using this, the polynomial time algorithm for VERTEX COVER and a deterministic rounding procedure we give a 2-approximation algorithm for OCT in perfect graphs.

(Joint work with N.S.Narayanaswamy and Venkatesh Raman)