TY - GEN

T1 - Paths of bounded length and their cuts

T2 - 4th International Workshop on Parameterized and Exact Computation, IWPEC 2009

AU - Golovach, Petr A.

AU - Thilikos, Dimitrios M.

PY - 2009

Y1 - 2009

N2 - We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem and the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length l of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both k and l and hardness results when the parameter is only one of k and l. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph.

AB - We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem and the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length l of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both k and l and hardness results when the parameter is only one of k and l. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph.

KW - Bounded length cuts

KW - Bounded length disjoint paths

KW - Parameterized algorithms

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=72249097356&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=72249097356&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-11269-0_17

DO - 10.1007/978-3-642-11269-0_17

M3 - Conference contribution

AN - SCOPUS:72249097356

SN - 3642112684

SN - 9783642112683

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 210

EP - 221

BT - Parameterized and Exact Computation - 4th International Workshop, IWPEC 2009, Revised Selected Papers

Y2 - 10 September 2009 through 11 September 2009

ER -