Everything About ___
Live briefing

Everything about Kernelization

Algorithmic technique

In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem. Wikipedia →

🧭 Start here: a 6-step reading path

  1. Read the overview: KernelizationA 5-minute orientation
  2. Skim a recent paper: Supervised dimensionality reduction technology of generalized discriminant component analysis and its kernelization formsInfluential work since 2022
  3. Pick up a classic book: Advances in large margin classifiersThe most-reprinted book on the subject
  4. Read the landmark paper: Invitation to data reduction and problem kernelizationCited 240 times
  5. Go sideways: Odd cycle transversalA closely related topic
  6. Go sideways: Parameterized complexityA closely related topic

📖 Definitions

Noun A technique for creating algorithms for fixed-parameter tractable problems, involving a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a kernel.

🗂️ The subject at a glance

  1. Example: vertex cover
  2. Definition
  3. Kernelizability and fixed-parameter tractability are equivalent
  4. More examples
  5. Kernelization for structural parameterizations

🏆 Landmark papers (most cited)

🆕 Influential since 2022

📚 Books worth reading

Ranked by number of editions on Open Library, a rough measure of how lasting a book is.

🔗 Related topics