\input zb-basic
\input zb-ioport
\iteman{io-port 06070903}
\itemau{Kawarabayashi, Ken-Ichi; Kobayashi, Yusuke}
\itemti{Edge-disjoint odd cycles in 4-edge-connected graphs.}
\itemso{D\"urr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th -- March 3rd, 2012. Wadern: Schloss Dagstuhl -- Leibniz Zentrum f\"ur Informatik (ISBN 978-3-939897-35-4). LIPICS -- Leibniz International Proceedings in Informatics 14, 206-217, electronic only (2012).}
\itemab
Summary: Finding edge-disjoint odd cycles is one of the most important problems in graph theory, graph algorithms and combinatorial optimization. In fact, it is closely related to the well-known max-cut problem. One of the difficulties of this problem is that the Erd\"os-P\'osa 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 4-edge-connected graph $G=(V,E)$, either $G$ has edge-disjoint $k$ odd cycles or there exists an edge set $F \subseteq E$ with $|F| \leq f(k)$ such that $G-F$ is bipartite. We note that the 4-edge-connectivity is best possible in this statement. Similar approach can be applied to an algorithmic question. Suppose that the input graph $G$ is a 4-edge-connected graph with $n$ vertices. We show that, for any $\varepsilon > 0$, if $k = O ((\log \log \log n)^{1/2-\varepsilon})$, then the edge-disjoint $k$ odd cycle packing in $G$ can be solved in polynomial time of $n$.
\itemrv{~}
\itemcc{}
\itemut{odd-cycles; disjoint paths problem; Erd\H{o}s-P\'osa property; packing algorithm; 4-edge-connectivity}
\itemli{doi:10.4230/LIPIcs.STACS.2012.206}
\end