Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs
Naonori Kakimura, Ken‐ichi Kawarabayashi, Yusuke Kobayashi · SIAM Journal on Discrete Mathematics · 2017
In this paper, we show the Erdös--Pósa property for edge-disjoint packing of $S$-closed walks with parity constraints in 4-edge-connected graphs. More precisely, we prove that for any 4-edge-connected graph $G$ and any vertex subset $S$, either $G$ has $k$ edge-disjoint elementary closed odd walks, each of which has at least one vertex of $S$, or $G$ has an edge set $F$ with $|F| \leq f(k)$ such that $G-F$ has no such walks. The 4-edge-connectivity is the best possible in the sense that 3-edge-connected graphs do not satisfy the statement. Since the proof is constructive, we can design a fixed-parameter algorithm for finding $k$ edge-disjoint walks satisfying the conditions in a 4-edge-connected graph for a parameter $k$. In addition, this gives a simple fixed-parameter algorithm for the parity edge-disjoint walks problem with $k$ terminal pairs.