Paths of bounded length and their cuts: Parameterized complexity and algorithms

Petr A. Golovach, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)72-86
Number of pages15
JournalDiscrete Optimization
Issue number1
StatePublished - Feb 2011


  • Bounded length cuts
  • Bounded length disjoint paths
  • Parameterized algorithms
  • Parameterized complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Paths of bounded length and their cuts: Parameterized complexity and algorithms'. Together they form a unique fingerprint.

Cite this