Parametrized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
| dc.contributor.author | Slivkins, Aleksandrs | en_US |
| dc.date.accessioned | 2007-04-04T19:20:36Z | |
| dc.date.available | 2007-04-04T19:20:36Z | |
| dc.date.issued | 2003-04-01 | en_US |
| dc.description.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 ditected acyclic graphs. 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(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. | en_US |
| dc.format.extent | 307076 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2003-1894 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/5610 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Parametrized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs | en_US |
| dc.type | technical report | en_US |
Files
Original bundle
1 - 1 of 1