Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems

DOI10.4230/LIPIcs.ICALP.2016.25zbMath1388.68111OpenAlexW2963972833MaRDI QIDQ4598161

Rolf Niedermeier, Till Fluschnik, Danny Hermelin, André Nichterlein

Publication date: 19 December 2017

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.25

zbMATH Keywords

lower boundsparameterized complexitygraph modification problemsinterdiction problemspolynomial-time data reductioncross-compositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ Parameterized complexity of length-bounded cuts and multicuts

This page was built for publication: Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems