Kawarabayashi, Kenichi ;
Kobayashi, Yusuke
Edgedisjoint Odd Cycles in 4edgeconnected Graphs
Abstract
Finding edgedisjoint odd cycles is one of the most important problems
in graph theory, graph algorithm and combinatorial optimization. In
fact, it is closely related to the wellknown maxcut problem. One of
the difficulties of this problem is that the ErdösPósa property does not hold for odd cycles in general. Motivated by this fact, we prove that for any positive integer k, there exists an integer f(k) satisfying the following: For any 4edgeconnected graph G=(V,E),
either G has edgedisjoint k odd cycles or there exists an edge set F
subseteq E with F <= f(k) such that GF is bipartite. We note that
the 4edgeconnectivity is best possible in this statement.
Similar approach can be applied to an algorithmic question. Suppose
that the input graph G is a 4edgeconnected graph with n vertices.
We show that, for any epsilon > 0, if k = O ((log log log n)^{1/2epsilon}), then the edgedisjoint k odd cycle packing in G can be solved in polynomial time of n.
BibTeX  Entry
@InProceedings{kawarabayashi_et_al:LIPIcs:2012:3417,
author = {Kenichi Kawarabayashi and Yusuke Kobayashi},
title = {{Edgedisjoint Odd Cycles in 4edgeconnected Graphs}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {206217},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3417},
URN = {urn:nbn:de:0030drops34173},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2012.206},
annote = {Keywords: oddcycles, disjoint paths problem, Erd{\"o}sPosa property, packing algorithm, 4edgeconnectivity }
}
2012
Keywords: 

oddcycles, disjoint paths problem, ErdösPosa property, packing algorithm, 4edgeconnectivity 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Related Scholarly Article: 


Issue date: 

2012 
Date of publication: 

2012 