Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
Lists
Only you see this
Abstract
Given a graph and pairs s i t i of terminals, the edge-disjoint paths problem is to determine whether there exist s i t i paths that do not share any edges. We consider this problem on acyclic digraphs. It is known to be NP-complete and solvable in time n O(k) where k is the number of paths. It has been a long-standing open question whether it is fixed-parameter tractable in k. We resolve this question in the negative: we show that the problem is W[1]-hard. In fact it remains W[1]-hard even if the demand graph consists of two sets of parallel edges. On a positive side, we give an O(m+k! n) algorithm for the special case when G is acyclic and G+H is Eulerian, where H is the demand graph. We generalize this result (1) to the case when G+H is “nearly" Eulerian, (2) to an analogous special case of the unsplittable flow problem. Finally, we consider a related NP-complete routing problem when only the first edge of each path cannot be shared, and prove that it is fixed-parameter tractable on directed graphs.
BibTeX
@inproceedings{slivkins2003parameterized,
author = {Aleksandrs Slivkins},
title = {{Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs}},
booktitle = {ESA},
year = {2003},
doi = {10.1007/978-3-540-39658-1\_44},
}Loading related content...