Fractals for kernelization lower bounds, with an application to length-bounded cut problems

DOI10.4230/LIPICS.ICALP.2016.25zbMATH Open1388.68111OpenAlexW2963972833MaRDI QIDQ4598161FDOQ4598161

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

Publication date: 19 December 2017

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

Recommendations

• Fractals for kernelization lower bounds
• Cross-composition: a new technique for kernelization lower bounds
• Kernelization Lower Bounds by Cross-Composition
• Lower bounds for kernelization
• On problems without polynomial kernels

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)

Cited In (6)

• On algorithms employing treewidth for \(L\)-bounded cut problems
• Parameterized complexity of length-bounded cuts and multicuts
• Elements of efficient data reduction: fractals, diminishers, weights and neighborhoods
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• Fractals for kernelization lower bounds
• Cross-composition: a new technique for kernelization lower bounds

This page was built for publication: Fractals for kernelization lower bounds, with an application to length-bounded cut problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598161)