Computer Science

Colloquium Details

Edge-disjoint odd cycles in planar graphs

Abstract

We study one of hitting set problems, usually called in this setting a vertex/edge feedback set problem. Hitting set problems are important combinatorial optimization problems. The goal is to find a (small) set of elements which intersect all sets in a given set system. The problem is NP-hard not only in general but also for most of special cases. Feedback set problems arise in lots of applications, e.g., circuit testing, AI, deadlock resolution, and manufacturing processes. Recent advances include efficient approximation algorithms based on linear programming (LP).

In this talk, we show how linear programming may provide interesting insights also from the combinatorial point of view. In the particular case of the hitting set problem, the set system is a set of all odd cycles in a planar graph. It turns out that the problem can be solved in polynomial time. To obtain this result, we prove that for any planar graph G, t(G)>=2n(G), where n(G) is the maximum number of edge-disjoint odd cycles and t(G) is the minimum number of edges whose removal makes G bipartite, i.e., the minimum size of the hitting set. Our linear bound is tight and it improves a previous fast growing bound due to Berge and Reed. Algorithmic aspects of our result will be discussed.

The talk will contain also an introduction to linear programming and it should also be understandable for people who have no previous experience with it.

This is joint work with Heinz-Juergen Voss.