TY - JOUR
T1 - Packing edge-disjoint odd Eulerian subgraphs through prescribed vertices in 4-edge-connected graphs
AU - Kakimura, Naonori
AU - Kawarabayashi, Ken Ichi
AU - Kobayashi, Yusuke
N1 - Funding Information:
This work is supported by JST, ERATO, the Kawarabayashi Large Graph Project, and KAKENHI grants JP24106002, JP24106003, JP24700004, and JP25730001.
Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2017
Y1 - 2017
N2 - In this paper, we show the Erdos-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| ≥ 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.
AB - In this paper, we show the Erdos-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| ≥ 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.
KW - Cycle packing
KW - Erdos-Pósa property
KW - Fixed-parameter algorithm
UR - http://www.scopus.com/inward/record.url?scp=85021888664&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85021888664&partnerID=8YFLogxK
U2 - 10.1137/15M1022239
DO - 10.1137/15M1022239
M3 - Article
AN - SCOPUS:85021888664
SN - 0895-4801
VL - 31
SP - 766
EP - 782
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 2
ER -