An Improved Algorithm for the Half-Disjoint Paths Problem
Ken‐ichi Kawarabayashi, Yusuke Kobayashi · SIAM Journal on Discrete Mathematics · 2011
In this paper, we consider the half-integral disjoint paths packing. For a graph [Formula: see text] and [Formula: see text] pairs of vertices [Formula: see text] in [Formula: see text], the objective is to find paths [Formula: see text] in [Formula: see text] such that [Formula: see text] joins [Formula: see text] and [Formula: see text] for [Formula: see text], and in addition, each vertex is on at most two of these paths. We give a polynomial-time algorithm to decide the feasibility of this problem with [Formula: see text]. This improves a result by Kleinberg [Proceedings of the 30th ACM Symposium on Theory of Computing, 1998, pp 530–539] who proved the same conclusion when [Formula: see text]. Our algorithm still works for several problems related to the bounded unsplittable flow. These results can all carry over to problems involving edge capacities. Our main technical contribution is to give a “crossbar” of a polynomial size of the tree width of the graph.