A nearly linear time algorithm for the half integral disjoint paths packing
Lists
Only you see this
Abstract
We consider the following problem, which is called the half integral parity disjoint paths packing problem. Input: A graph G, k pair of vertices (s1, t1), (s2, t2),..., (sk, tk) in G (which are sometimes called terminals), and a parity li for each i with 1 ≤ i ≤ k, where li = 0 or 1. Output: Paths P1,..., Pk in G such that Pi joins si and ti for i = 1, 2,..., k and parity of length of the path Pi is li, i.e, if li = 0, then length of Pi is even, and if li = 1, then length of Pi is odd for i = 1, 2,..., k. In addition, each vertex is on at most two of these paths. We present an O(mα(m, n) log n) algorithm for fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function α(m, n) is the inverse of the Ackermann function (see by Tarjan [43]). This is the first polynomial time algorithm for this problem, and generalizes polynomial time algorithms by Kleinberg [23] and Kawarabayashi and Reed [20], respectively, for the half integral disjoint paths packing problem, i.e., without the parity requirement. As with the Robertson-Seymour algorithm to solve the k disjoint paths problem, 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 paths 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. We also have algorithms running in O(m (1+ε)) time for any ε> 0 for this problem, if k is up to o(log log log n) for general graphs, up to o(log log n) for
BibTeX
@inproceedings{kawarabayashi2008nearly,
author = {Ken-ichi Kawarabayashi and Bruce A. Reed},
title = {{A nearly linear time algorithm for the half integral disjoint paths packing}},
booktitle = {SODA},
year = {2008},
}Loading related content...