ABSTRACT
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 m1/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(m1/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.
- . Arnborg and A. Proskurowski,Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math., 23 (1989), 11--24. Google ScholarDigital Library
- . Balister, packing digraphs with directed closedtrails, Combin. Probab. Comput., 12 (2003), 1--15. Google ScholarDigital Library
- . L. Bodlaender,A linear-time algorithm for finding tree-decomposition of smalltreewidth, SIAM J. Comput., 25 (1996), 1305--1317. Google ScholarDigital Library
- . Böhme,K. Kawarabayashi, J. Maharry and B. Mohar,Linear connectivity forces large complete bipartite minors, J. Combin. Theory Ser. B., 99 (2009), 557--582. Google ScholarDigital Library
- . Chekuri and S. Khanna,Edge disjoint paths revisited, ACM-SIAM Symposium on Discrete Algorithms (SODA'03), 628--637, (2003). Google ScholarDigital Library
- . Chudnovsky, J. Geelen, B. Gerards, L. Goddyn, M. Lohmanand P. Seymour, Packing non-zero A-paths in group labelled graphs, Combinaorica, 26 (2006), 521--532. Google ScholarDigital Library
- . Dejter and V. Neumann-lara,Unboundedness for generalized odd cycle traversability anda Gallai conjecture, paper presented at the Fourth Caribbean Conference on Computing, Puerto Rico, 1985.Google Scholar
- . D. Demaine, M. Hajiaghayi, and K. Kawarabayashi,Algorithmic graph minor theory: Decomposition, approximation and coloring,Proc. 46th Annual Symposium on Foundations of Computer Science (FOCS'06),637--646, (2005). Google ScholarDigital Library
- . Diestel, K. Yu. Gorbunov, T. R. Jensen, and C. Thomassen,Highly connected sets and the excluded grid theorem, J. Combin. Theory Ser. B, 75 (1999), 61--73. Google ScholarDigital Library
- R. Diestel, K. Kawarabayashi, T. Müller and P. Wollan,On the structure theorem of the excluded minor theorem of large tree-width, submitted.Google Scholar
- . Erdös and L. Pósa,On the maximal number of disjoint circuits of a graph, Publ. Math. Debrecen, 9 (1962), 3--12.Google Scholar
- . Fortune, J.E. Hopcroft and J. Wyllie,The directed subgraph homeomorphism problem, Theor. Comput. Sci., 10 (1980), 111--121.Google ScholarCross Ref
- . Fiorini, N. Hardy, B. Reed and A. Vetta,Approximate min-max relations for odd cycles in planar graphs, Mathematical Programming, 110 (2007), 71--91. Google ScholarDigital Library
- . Frank,Packing paths, cuts and circuits -- a survey, in Paths, Flows and VLSI-Layout B. Korte, L. Lovász, H.J. Promel and A. Schrijver. Eds.Berlin: Springer-Verlag 1990, 49--100.Google Scholar
- . Geelen, B. Gerards, B. Reed, P. Seymourand A. Vetta, On the odd variant of Hadwiger's conjecture, J. Combin. Theory Ser. B., 99 (2009),20--29. Google ScholarDigital Library
- . X. Goemans and D.P. Williamson, Primal-dual approximation algorithms for feedback problems in planar graphs, Combinatorica, 18 (1998), 37--59.Google Scholar
- . Guruswami, S. Khanna, R. Rajaraman, B. Sherphard, and M. Yannakakis,Near-optimal hardness results and apprixmaiton algorithms for edge-disjoint paths andrelated problems, J. Comp. Styst. Science, 67 (2003), 473--496.Also, Proc. 31st ACM Symposium on Theory of Computing, (STOC'99), 19--28, (1999).%530--539. Google ScholarDigital Library
- . Hadlock,Finding a maximum cut of a planar graph in polynomial time, Siam J. Comput., 4 (1975), 221--225.Google ScholarCross Ref
- . Halin, S-function for graphs, J. Geometry, 8 (1976), 171--186.Google ScholarCross Ref
- . Hunyh,The linkage problem for group-labelled graphs, Ph. D Thesis,University of Waterloo, 2009.Google Scholar
- . Ibaraki and H. Nagamochi,A linear time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph, Algorithmica, 7(1992), 583--596.Google Scholar
- . Kapadia, Z. Li and B. Reed,A linear time algorithm to test the 2-paths problem, submitted.Google Scholar
- . Kawarabayashi,On the connectivity of minimal counterexamples to Hadwiger's conjecture, J. Combin. Theory Ser. B, 97 (2007), 144--150. Google ScholarDigital Library
- . Kawarabayashi,Rooted minors problem in highly connected graphs, Discrete Math., 287 (2004), 121--123.Google ScholarCross Ref
- . Kawarabayashi,Improved alogirthm for find a cycle through elements, IPCO'08, 374--384. Google ScholarDigital Library
- . Kawarabayashi,Note on coloring graphs with no odd-K-k-minors, J. Combin. Theory Ser. B., 99 (2009),738--741. Google ScholarDigital Library
- . Kawarabayashi and P. Wollan,Non-zero disjoint cycles in highly connected group-labelled graphs, J. Combin. Theory Ser. B, 96(2006), 296--301. Google ScholarDigital Library
- . Kawarabayashi and Z. Song,Some remarks on the odd Hadwiger's conjecture, Combinatorica, 27 (2007), 429--438. Google ScholarDigital Library
- . Kawarabayashi and A. Nakamoto,The Erdos-Pósa property for odd cycles on an orientable fixed surface, Discrete Math., 307 (2007), 764--768.Google Scholar
- . Kawarabayashi and B. Reed,Computing crossing number in linear time, Proc. 39th ACM Symposium on Theory of Computing (STOC'07), 382--390, (2007). Google ScholarDigital Library
- . Kawarabayashi and B. Mohar,Graph and Map Isomorphism and all polyhedral embeddings in linear time, Proc. 40th ACM Symposium on Theory of Computing (STOC'08), 471--480, (2008). Google ScholarDigital Library
- . Kawarabayashi and B. Reed,A nearly linear time algorithm for the half disjoint paths packing, ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 446--454, (2008). Google ScholarDigital Library
- . Kawarabayashi and B. Reed,A nearly linear time algorithm for the half integral parity disjoint paths packing problem (with B. Reed), ACM-SIAM Symposium on Discrete Algorithms (SODA'09), 1183--1192, (2009). Google ScholarDigital Library
- . Kawarabayashi and B. Reed,Highly parity linked graphs, Combinatorica, 29 (2009), 215--225. Google ScholarDigital Library
- . Kawarabayashi, B. Mohar and B. Reed,A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of bounded tree-width graphs, Proc. 49th Annual Symposium on Foundations of Computer Science (FOCS'08),771--780, (2008). Google ScholarDigital Library
- . Kawarabayashi, Y. Kobayashi and B. Reed,The disjoint paths problem in quaratic time, submitted.Google Scholar
- . Kawarabayashi and B. Reed,An (almost) linear time algorithm for odd cycles transversal, ACM-SIAM Symposium on Discrete Algorithms, (SODA'10), 365--378, (2010). Google ScholarDigital Library
- . M. Karp,On the computational complexity of combinatorial problems, Network, 5 (1975), 45--68.Google ScholarDigital Library
- . Kostochka,Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica, 4 (1984), 307--316.Google ScholarCross Ref
- . Kostochka,The minimum Hadwiger number for graphs with a given mean degree of vertices(in Russian), Metody Diskret. Analiz. 38 (1982), 37--58.Google Scholar
- . Krivelevich, Z. Nutov, M. R. Salavatipour, J.Verstaete, and R. Yuster, Approximating algorithms and hardnessresults for cycle packing problems, ACM transaction onAlgorithms, 3 (2007), article 48. Also, SODA 2005 and IPCO2005. Google ScholarDigital Library
- . Mohar,Combinatorial local planarity and the width of graph embeddings, Canad. J. Math., 44 (1992), 1272--1288.Google ScholarCross Ref
- B. Mohar and C. Thomassen,Graphs on Surfaces,Johns Hopkins University Press, Baltimore, MD, 2001.Google Scholar
- . Perkovic and B. Reed,An improved algorithm for finding tree decompositions of small width, International Journal on the Foundations of Computing Science, 11 (2000), 81--85.Google ScholarCross Ref
- . Reed,Finding approximate separators and computing tree width quickly; STOC 1992, Victoria B.C., 1992. Google ScholarDigital Library
- . Reed,Rooted Routing in the Plane, Discrete Applied Mathematics, 57 (1995), 213--227. Google ScholarDigital Library
- . Reed,Tree width and tangles: a new connectivity measure and some applications,in "Surveys in Combinatorics, 1997 (London)",London Math. Soc. Lecture Note Ser. 241,Cambridge Univ. Press, Cambridge, 1997, pp. 87--162.Google Scholar
- . Reed,Mangoes and blueberries, Combinatorica, 19 (1999), 267--296.Google ScholarCross Ref
- . Reed,Rooted Routing via Graph Minors, to appear.Google Scholar
- B. Reed, N. Robertson, A. Schrijver and P. D. Seymour,Finding disjoint trees in planar graphs in linear time. Graph structure theory (Seattle, WA, 1991), 295--301, Contemp. Math., 147, Amer. Math. Soc., Providenc, RI, 1993.Google Scholar
- . Reed, K. Smith and A. Vetta,Finding odd cycle transversals, Operation Research Letter, 32(2004), 299--301. Google ScholarDigital Library
- B. Reed and D. Wood,A linear time algorithm to find a separator in a graph with anexcluded minor, submitted.Google Scholar
- . Rizzi, V. Bafna, S. Istrail, G. Lancia,Practical algorithms and fixed parameter tractability for the single individual SNP haplo typing problem, Algorithms in Bioinformatics:Second international workshop, Lecture notes in computer scienece, 2452, Springer, Berlin, 2002, 29--43. Google ScholarDigital Library
- . Robertson and P. D. Seymour,Graph minors. III. Planar tree-width, J. Combin. Theory Ser. B, 36 (1984), 49--63.Google ScholarCross Ref
- . Robertson and P. D. Seymour,Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B, 41 (1986), 92--114. Google ScholarDigital Library
- N. Robertson and P. D. Seymour, Graphminors. VII. Disjoint paths on a surface, J. Combin. Theory Ser. B, 45 (1988), 212--254. Google ScholarDigital Library
- N. Robertson and P. D. Seymour, Graphminors. IX. Disjoint crossed paths, J. Combin. Theory Ser. B, 49 (1990), 40--77. Google ScholarDigital Library
- N. Robertson and P. D. Seymour, Graphminors. X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52 (1991), 153--190. Google ScholarDigital Library
- N. Robertson and P. D. Seymour,Graph minors. XI. Circuits on a surface, J. Combin. Theory Ser. B, 60 (1994), 72--106. Google ScholarDigital Library
- . Robertson and P. D. Seymour,Graph minors. XII.Distance on a surface, J. Combin. Theory, Ser. B, 64(1995), 240--272. Google ScholarDigital Library
- . Robertson and P. D. Seymour,Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63 (1995), 65--110. Google ScholarDigital Library
- . Robertson and P. D. Seymour,Graph minors. XVI. Excluding a non--planar graph, J. Combin. Theory Ser. B, 89 (2003), 43--76. Google ScholarDigital Library
- . Robertson and P. D. Seymour,Graph minors. XVII. Taming a vortex, J. Combin. Theory Ser. B, 77 (1999), 162--210. Google ScholarDigital Library
- . Robertson and P. D. Seymour,Graph Minors XXI. Graphs with uniquely linkages,to appear in J. Combin. Theory Ser. B. Google ScholarDigital Library
- N. Robertson and P. D. Seymour,Graph Minors XXII. Irrelevant vertices in linkage problems,to appear in J. Combin. Theory Ser. B. Google ScholarDigital Library
- . Robertson and P. D. Seymour,An outline of a disjoint paths algorithm,in: "Paths, Flows, and VLSI-Layout,"B. Korte, L. Lovász, H. J. Prömel, and A. Schrijver (Eds.),Springer-Verlag, Berlin, 1990, pp. 267--292.Google Scholar
- . Robertson, P. D. Seymour and R. Thomas,Quickly excluding a planar graph, J. Combin. Theory Ser. B, 62 (1994), 323--348. Google ScholarDigital Library
- . Schrijver,Combinatorial Optimization: Polyhedra and Efficiency, number 24 inAlgorithm and Combinatorics, Springer Verlag, 2003.Google Scholar
- .D. Seymour,Decomposition of regular matroids. J. Combin. Theory, Ser. B, 28 (1980),305--359.Google ScholarCross Ref
- P. Seymour, Disjoint paths in graphs, Discrete Mathematics, 29(1980),293 -- 309.Google ScholarDigital Library
- . Seymour, Matroid minors, Handbook of Combinatorics,(Eds.: R. L. Graham, M. Grötschel and L. Lóvasz). North-Holland,Amsterdam, 1985, 419--431. Google ScholarDigital Library
- . Seymour and R. Thomas,Graph searching and a min-max theorem for tree-width, J. Combin. Theory Ser. B, 58 (1993), 22--33. Google ScholarDigital Library
- .E. Tarjan,Data Structures and network algorithms, SIAM, Philadelphia, PA, 1983. Google ScholarDigital Library
- . Tholey,Solving the 2-disjoint paths problem in nearly linear time, Theory of computing systems, 39 (2004), 51--78.Google Scholar
- . Thomason,An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc., 95 (1984), 261--265.Google ScholarCross Ref
- . Thomason,The extremal function for complete minors, J. Combin. Theory Ser. B, 81 (2001), 318--338. Google ScholarDigital Library
- C. Thomassen,2-linked graph, European J. Combinatorics, 1(1980),371 -- 378.Google ScholarCross Ref
- C. Thomassen,On the presence of disjoint subgraphs of a specified type, J. Graph Theory, 12(1988),101 -- 111.Google ScholarCross Ref
- . Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 114 (1937), 570---590.Google ScholarCross Ref
Index Terms
- Odd cycle packing
Recommendations
Rainbow Odd Cycles
We prove that every family of (not necessarily distinct) odd cycles $O_1, \dots, O_{2\lceil n/2 \rceil-1}$ in the complete graph $K_n$ on $n$ vertices has a rainbow odd cycle (that is, a set of edges from distinct $O_i$'s, forming an odd cycle). As part ...
Edge-disjoint odd cycles in 4-edge-connected graphs
Finding edge-disjoint odd cycles is one of the most important problems in graph theory, graph algorithms and combinatorial optimization. One of the difficulties of this problem is that the Erd s-Pósa property does not hold for odd cycles in general. ...
Adjacency eigenvalues of graphs without short odd cycles
AbstractIt is well known that spectral Turán type problem is one of the most classical problems in graph theory. In this paper, we consider the spectral Turán type problem. Let G be a graph and let G be a set of graphs, we say G is G ...
Comments