CS 789 THEORY SEMINAR [home]

Speaker:  Alex Slivkins     
Affiliation: Computer Science, Cornell University
Date: Monday, February 18, 2002
Title: Network Congestion, Disjoint Paths and Parameterized Complexity

Abstract: 

We propose several variants of the Disjoint Paths problem, motivated by the issues of network congestion. In one model we are interested in finding paths between $k$ pairs of terminals such that the first edge of each path cannot be shared with any other path. We prove that this problem is fixed-parameter tractable on directed graphs, in contrast to Disjoint Paths which is known to be NP-hard even for two paths. We also consider a more general first-node-disjoint analog of this problem.

Another model, bottleneck-edge-disjoint paths, is a generalization of Disjoint Paths. For directed acyclic graphs, we show that bottleneck-edge-disjoint paths is W[1]-hard and hence unlikely to be fixed-parameter tractable. We give an algorithm that runs in time $n^{O(k)}$. These two results easily extend to Unsplittable Flows.

Joint work with Jon Kleinberg and Martin Pal