Campus Event Calendar

Event Entry

What and Who

LP Approach to Odd Cycle Transversal in Perfect Graphs

R. Krithika
Indian Institute of Technology Madras
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience

Date, Time and Location

Tuesday, 13 August 2013
30 Minutes
E1 4


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)


Krithika Ramaswamy
--email hidden
passcode not visible
logged in users only

Krithika Ramaswamy, 08/02/2013 11:06
Krithika Ramaswamy, 08/02/2013 11:05 -- Created document.