STOC Conference 2010 Conference Paper
- Ken-ichi Kawarabayashi
- Bruce A. Reed
We consider the following problem, which is called the odd cycle packing problem . Input: A graph $G$ with n vertices and m edges, and an integer k. Output: k vertex disjoint odd cycles. We also consider the edge disjoint case, and the node- and arc-disjoint directed case. This problem is known to be NP-hard, even for planar graphs, if k is part of input. In this paper, we first present the integrality gap and hardness results for these problems. We prove that the integrality gap of the standard LP-relaxation of the odd cycle packing problem is Θ (√n). This result is obtained by giving an algorithm to compute an odd cycle packing, which gives rise to an O(√n) approximating algorithm for the fractional odd cycle packing problem (this gives rise to an upper bound), and by showing that there is a graph G such that there is an O(√n) half-integral odd cycle packing in G, but there are no two disjoint odd cycle in G (this gives rise to a lower bound). For the hardness result, we prove that for any ε, the node-disjoint directed odd cycle packing problem is NP-hard to approximate within m 1/2-ε , where m is the number of arcs of a given digraph G. This is true not only for the node-disjoint directed odd cycle packing problem but also for the arc-disjoint directed odd cycle packing problem. In addition, we prove that there is an O(m 1/2 )-approximation algorithm for the node- and arc- directed odd cycle packing problems. Thus this approximation algorithm almost matches the hardness result. For the positive side, we consider the case when the number of odd cycles, k, is fixed. This is a natural direction, for example, the seminal result of Robertson and Seymour for the disjoint paths problem in the graph minors project. We present an O(m α(m,n) n) algorithm for any fixed k, where the function α(m,n) is the inverse of the Ackermann function (see by Tarjan [72]). This is the first polynomial time algorithm for this problem (and in fact, it is the first fixed parameter tractable algorithm). This proves a conjecture by Lovasz and Schrijver in early 1980's, who gave a polynomial time algorithm for the case k=2. Our algorithm can be applied to decide whether or not G has k edge disjoint odd cycle with the same time complexity for any fixed k. We also show that our algorithm gives rise to the Graph Minor Algorithm for the k vertex-disjoint paths problem by Robertson and Seymour for any fixed k. Thus our algorithm is beyond the framework of the Graph Minor Theory. Our algorithm has several appealing features: We use the odd S-path theorem, which is a generalization of the well-known S-paths theorem by Mader. We also introduce an odd clique minor, which can be viewed as a clique minor with some parity condition. As with the Robertson-Seymour algorithm to solve the k disjoint paths problem for any fixed k, in each iteration, we would like to either use a huge clique minor as a "crossbar", or exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the cycles and can only use an "odd clique minor". We must also describe the structure of those graphs in which we cannot find such a minor and discuss how to exploit it. This part needs the seminal result of Robertson and Seymour for the graph minor decomposition theorem for H-minor-free graphs. We also use some deep results of Robertson and Seymour that are needed to prove the correctness of their algorithm for the disjoint paths problem.