| Title | : | Parameterized and Approximation Algorithms for Finding Hitting Sets |
| Speaker | : | Krithika.R (IITM) |
| Details | : | Fri, 16 Oct, 2015 2:00 PM @ BSB 361 |
| Abstract: | : | Abstract: An odd cycle transversal of a graph is a set of vertices that has a non-empty intersection with the vertex set of every odd cycle. In other words, its deletion results in a bipartite (2-colorable) graph. Such sets generalize vertex covers as a vertex cover is a set of vertices whose deletion results in an edgeless (1-colorable) graph. The fixed-parameter tractability of finding an odd cycle transversal of size k was settled using an algorithmic technique which is now called iterative compression. In the first part of the talk, we present another parameterized algorithm of the same time complexity using this technique and a reduction to finding minimum vertex cover in a bipartite graph. This algorithm is conceptually simpler than the known algorithms for the problem and refines the understanding of the relationship between odd cycle transversal and vertex cover. We then discuss the complexity of finding minimum odd cycle transversals that have additional properties. The second part of the talk is on approximation approaches to the problem of finding a minimum r-clique transversal in perfect graphs. A set of vertices is an r-clique transversal if it has at least one vertex from every r-clique. One of the largest classes of graphs on which a minimum vertex cover (2-clique transversal) can be obtained in polynomial time is the family of perfect graphs. However, finding a minimum r-clique transversal is NP-hard even for r = 3. We describe multiple approaches to this problem based on linear programming and show that it admits an (r + 1)/2-approximation thus improving on the straightforward r-approximation. The algorithms are obtained through appealing to the theta function computation, the polyhedral characterization of perfect graphs based on the vertex cover polytope description, the primal-dual method and the approximability of vertex cover in r-partite hypergraphs. |
