2009 | OriginalPaper | Buchkapitel
Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms
verfasst von : Petr A. Golovach, Dimitrios M. Thilikos
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.