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

DOI10.4230/LIPICS.ICALP.2016.25MaRDI QIDQ4598161zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(7)

• Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
• On algorithms employing treewidth for \(L\)-bounded cut problems
• Parameterized complexity of length-bounded cuts and multicuts
• Cross-composition: a new technique for kernelization lower bounds
• Fractals for kernelization lower bounds
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• Elements of efficient data reduction: fractals, diminishers, weights and neighborhoods

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)