Kernelization complexity of solution discovery problems

DOI10.4230/LIPICS.ISAAC.2024.36MaRDI QIDQ7260654zbMATH OpenFDO

Authors Stephanie Maaz, Amer E. Mouawad, N. Nishimura, Vijayaragunathan Ramamoorthi, Sebastian Siebertz

Publication date 8 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2024.36

zbMATH Keywords

cutdominating setindependent setkernelizationsolution discoveryvertex cover

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Advice classes of parametrized tractability
• Complexity results for rainbow matchings
• Fundamentals of parameterized complexity
• Infeasibility of instance compression and succinct PCPs for NP
• Intersection Theorems for Systems of Sets
• Introduction to reconfiguration
• Kernelization Lower Bounds by Cross-Composition
• On problems without polynomial kernels
• On the number of types in sparse graphs
• Parameterized algorithms
• Polynomial kernels and wideness properties of nowhere dense graph classes
• Solution discovery via reconfiguration for problems in P
• Some consequences of non-uniform conditions on uniform classes

This page was built for publication: Kernelization complexity of solution discovery problems

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