article

Invitation to data reduction and problem kernelization

Authors:

Rolf NiedermeierAuthors Info & Claims

ACM SIGACT News, Volume 38, Issue 1

Pages 31 - 45

https://doi.org/10.1145/1233481.1233493

Published: 01 March 2007 Publication History

Abstract

To solve NP-hard problems, polynomial-time preprocessing is a natural and promising approach. Preprocessing is based on data reduction techniques that take a problem's input instance and try to perform a reduction to a smaller, equivalent problem kernel. Problem kernelization is a methodology that is rooted in parameterized computational complexity. In this brief survey, we present data reduction and problem kernelization as a promising research field for algorithm and complexity theory.

References

[1]

F. N. Abu-Khzam, R. L. Collins, M. R. Fellows, M. A. Langston, W. H. Suters, and C. T. Symons. Kernelization algorithms for the Vertex Cover problem: Theory and experiments. In Proc. 6th ACM-SIAM ALENEX, pages 62--69. ACM-SIAM, 2004.

[2]

J. Alber, B. Dorn, and R. Niedermeier. A general data reduction scheme for domination in graphs. In Proc. 32nd SOFSEM, volume 3831 of LNCS, pages 137--147. Springer, 2006.

Digital Library

[3]

J. Alber, M. R. Fellows, and R. Niedermeier. Polynomial time data reduction for Dominating Set. Journal of the ACM, 51(3):363--384, 2004.

Digital Library

[4]

B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153--180, 1994.

Digital Library

[5]

R. E. Bixby. Solving real-world linear programs: A decade and more of progress. Operations Research, 50:3--15, 2002.

Digital Library

[6]

H. L. Bodlaender. A cubic kernel for feedback vertex set. In Proc. 24th STACS, LNCS. Springer, 2007.

Digital Library

[7]

K. Burrage, V. Estivill-Castro, M. Fellows, M. Langston, S. Mac, and F. Rosamond. The undirected Feedback Vertex Set problem has a poly(k) kernel. In Proc. 2nd IWPEC, volume 4196 of LNCS, pages 192--202. Springer, 2006.

Digital Library

[8]

M. Cadoli, F. M. Donini, P. Liberatore, and M. Schaerf. Preprocessing of intractable problems. Information and Computation, 176(2):89--120, 2002.

Digital Library

[9]

L. Cai, J. Chen, R. G. Downey, and M. R. Fellows. Advice classes of parameterized tractability. Annals of Pure and Applied Logic, 84:119--138, 1997.

[10]

M. Charikar, V. Guruswami, and A. Wirth. Clustering with qualitative information. Journal of Computer and System Sciences, 71(3):360--383, 2005.

Digital Library

[11]

J. Chen, H. Fernau, I. A. Kanj, and G. Xia. Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. In Proc. 22nd STACS, volume 3404 of LNCS, pages 269--280. Springer, 2005.

Digital Library

[12]

J. Chen, I. A. Kanj, and W. Jia. Vertex Cover: Further observations and further improvements. Journal of Algorithms, 41:280--301, 2001.

Digital Library

[13]

B. Chor, M. Fellows, and D. W. Juedes. Linear kernels in linear time, or how to save k colors in O(n ²) steps. In Proc. 30th WG, volume 3353 of LNCS, pages 257--269. Springer, 2004.

Digital Library

[14]

P. Damaschke. Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theoretical Computer Science, 351(3):337--350, 2006.

Digital Library

[15]

I. Dinur and S. Safra. The importance of being biased. In Proc. 34th ACM STOC, pages 33--42. ACM, 2002.

Digital Library

[16]

R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer, 1999.

Digital Library

[17]

V. Estivill-Castro, M. R. Fellows, M. A. Langston, and F. Rosamond. FPT is P-time extremal structure I. In Proc. 1st ACiD, volume 4 of Texts in Algorithmics, pages 1--41. King's College, 2005.

[18]

J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006.

Digital Library

[19]

J. Gramm, J. Guo, F. Hüffner, and R. Niedermeier. Graph-modeled data clustering: Exact algorithms for clique generation. Theory of Computing Systems, 38(4):373--392, 2005.

Digital Library

[20]

J. Gramm, J. Guo, F. Hüffner, and R. Niedermeier. Data reduction, exact, and heuristic algorithms for Clique Cover. In Proc. 8th ACM-SIAM ALENEX, pages 86--94. ACM-SIAM, 2006. Long version to appear in The ACM Journal of Experimental Algorithmics.

Digital Library

[21]

J. Guo. A more effective linear kernelization for Cluster Editing, November 2006. Submitted.

[22]

J. Guo and R. Niedermeier. Fixed-parameter tractability and data reduction for Multicut in Trees. Networks, 46(3):124--135, 2005.

Digital Library

[23]

J. Guo, R. Niedermeier, and S. Wernicke. Parameterized complexity of generalized Vertex Cover problems. In Proc. 9th WADS, volume 3608 of LNCS, pages 36--48. Springer, 2005. Long version to appear under the title "Parameterized complexity of Vertex Cover variants" in Theory of Computing Systems.

Digital Library

[24]

J. Guo, R. Niedermeier, and S. Wernicke. Fixed-parameter tractability results for full-degree spanning tree and its dual. In Proc. 2nd IWPEC, volume 4196 of LNCS, pages 203--214. Springer, 2006.

Digital Library

[25]

F. Hüffner, R. Niedermeier, and S. Wernicke. Techniques for practical fixed-parameter algorithms. To appear in The Computer Journal, 2007.

[26]

S. Khot and O. Regev. Vertex Cover might be hard to approximate to within 2 - ε. In Proc. 18th IEEE Annual Conference on Computational Complexity, pages 379--386. IEEE, 2003.

[27]

P. Liberatore. Monotonic reductions, representative equivalence, and compilation of intractable problems. Journal of the ACM, 48(6):1091--1125, 2001.

Digital Library

[28]

D. Marx. Parameterized complexity and approximation algorithms. To appear in The Computer Journal, 2007.

Digital Library

[29]

G. L. Nemhauser and L. E. Trotter. Vertex packing: Structural properties and algorithms. Mathematical Programming, 8:232--248, 1975.

Digital Library

[30]

R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.

[31]

R. Niedermeier and P. Rossmanith. A general method to speed up fixed-parameter-tractable algorithms. Information Processing Letters, 73:125--129, 2000.

Digital Library

[32]

W. V. Quine. The problem of simplifying truth functions. American Mathematical Monthly, 59:512--531, 1952.

[33]

M. Weston. A fixed-parameter tractable algorithm for matrix domination. Information Processing Letters, 90:267--272, 2004.

Digital Library

Cited By

Lokshtanov DRamanujan MSaurabh SSharma RZehavi M(2025)Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for Directed Feedback Vertex SetACM Transactions on Computation Theory10.1145/371166917:1(1-28)Online publication date: 14-Feb-2025
https://dl.acm.org/doi/10.1145/3711669
Gahlawat HZehavi MWooldridge MDy JNatarajan S(2024)Learning small decision trees with few outliersProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i11.29098(12100-12108)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i11.29098
Himmel AMertzios GNichterlein ANiedermeier R(2024)Fast Parameterized Preprocessing for Polynomial-Time Solvable Graph ProblemsCommunications of the ACM10.1145/362471367:4(70-79)Online publication date: 25-Mar-2024
https://dl.acm.org/doi/10.1145/3624713
Show More Cited By

Index Terms

Invitation to data reduction and problem kernelization

Recommendations

Lower bounds on kernelization

Preprocessing (data reduction or kernelization) to reduce instance size is one of the most commonly deployed heuristics in the implementation practice to tackle computationally hard problems. However, a systematic theoretical study of them has remained ...
Kernelization Lower Bounds Through Colors and IDs

In parameterized complexity, each problem instance comes with a parameter k, and a parameterized problem is said to admit a polynomial kernel if there are polynomial time preprocessing rules that reduce the input instance to an instance with size ...
A Completeness Theory for Polynomial (Turing) Kernelization

The framework of Bodlaender et al. (J Comput Sys Sci 75(8):423---434, 2009 ) and Fortnow and Santhanam (J Comput Sys Sci 77(1):91---106, 2011 ) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGACT News

ACM SIGACT News Volume 38, Issue 1

March 2007

58 pages

ISSN:0163-5700

DOI:10.1145/1233481

Issue’s Table of Contents

Copyright © 2007 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2007

Published in SIGACT Volume 38, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

292
Total Citations
View Citations
1,167
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)4

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lokshtanov DRamanujan MSaurabh SSharma RZehavi M(2025)Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for Directed Feedback Vertex SetACM Transactions on Computation Theory10.1145/371166917:1(1-28)Online publication date: 14-Feb-2025
https://dl.acm.org/doi/10.1145/3711669
Gahlawat HZehavi MWooldridge MDy JNatarajan S(2024)Learning small decision trees with few outliersProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i11.29098(12100-12108)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i11.29098
Himmel AMertzios GNichterlein ANiedermeier R(2024)Fast Parameterized Preprocessing for Polynomial-Time Solvable Graph ProblemsCommunications of the ACM10.1145/362471367:4(70-79)Online publication date: 25-Mar-2024
https://dl.acm.org/doi/10.1145/3624713
Bumpus BJansen Bde Kroon J(2024)Search-Space Reduction via Essential VerticesSIAM Journal on Discrete Mathematics10.1137/23M158934738:3(2392-2415)Online publication date: 30-Aug-2024
https://doi.org/10.1137/23M1589347
Donkers HJansen B(2024)Preprocessing to reduce the search spaceJournal of Computer and System Sciences10.1016/j.jcss.2024.103532144:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.jcss.2024.103532
Jacob AMajumdar DRaman V(2023)Expansion Lemma—Variations and Applications to Polynomial-Time PreprocessingAlgorithms10.3390/a1603014416:3(144)Online publication date: 6-Mar-2023
https://doi.org/10.3390/a16030144
Chen HJansen BOkrasa KPieterse ARzążewski P(2023)Sparsification Lower Bounds for List H-ColoringACM Transactions on Computation Theory10.1145/361293815:3-4(1-23)Online publication date: 15-Sep-2023
https://dl.acm.org/doi/10.1145/3612938
Agrawal ALokshtanov DMisra PSaurabh SZehavi M(2023)Polynomial Kernel for Interval Vertex DeletionACM Transactions on Algorithms10.1145/357107519:2(1-68)Online publication date: 15-Apr-2023
https://dl.acm.org/doi/10.1145/3571075
Aggarwal DKumar R(2023)Why we couldn’t prove SETH hardness of the Closest Vector Problem for even norms!2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00138(2213-2230)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00138
Sou KLu J(2022)Relaxed Connected Dominating Set Problem for Power System Cyber–Physical SecurityIEEE Transactions on Control of Network Systems10.1109/TCNS.2022.31650889:4(1780-1792)Online publication date: Dec-2022
https://doi.org/10.1109/TCNS.2022.3165088
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents