| Title | : | Finding Odd Cycle Transversals in Perfect Graphs |
| Speaker | : | Krithika.R (IITM) |
| Details | : | Tue, 31 Mar, 2015 3:00 PM @ BSB 361 |
| Abstract: | : | Given an undirected simple graph, a set of vertices is an odd cycle transversal if it has at least one vertex from every odd cycle. Equivalently, the graph obtained by deleting such a set is bipartite. Odd cycle transversals generalize the classical vertex covers in a natural way. One of the largest classes of graphs on which a minimum vertex cover can be obtained in polynomial time is the class of perfect graphs. Perfect graphs, introduced by Claude Berge, link various areas of mathematics like graph theory, combinatorial optimization, mathematical programming,information theory, geometry, convexity theory and polyhedral theory. Perfect graphs also have nice algorithmic properties. They can be recognized in polynomial time and are amenable to polynomial-time algorithms based on semi-denite programming. However, finding a minimum odd cycle transversal is NP-hard on perfect graphs. We study the complexity of this problem on weighted perfect graphs and show that it admits a 2-approximation. Our algorithm is obtained through appealing to the Lovasz theta function computation and the polyhedral characterization of perfect graphs based on the vertex cover polytope description. We then show hardness results in the approximation and parameterized settings. |
