AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (237.2 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Kernelization in Parameterized Computation: A Survey

Qilong Feng, Qian Zhou, Wenjun Li, Jianxin Wang( )
School of Information Science and Engineering, Central South University, Changsha 410083, China.
Show Author Information

Abstract

Parameterized computation is a new method dealing with NP-hard problems, which has attracted a lot of attentions in theoretical computer science. As a practical preprocessing method for NP-hard problems, kernelizaiton in parameterized computation has recently become an active research area. In this paper, we discuss several kernelizaiton techniques, such as crown decomposition, planar graph vertex partition, randomized methods, and kernel lower bounds, which have been used widely in the kernelization of many hard problems.

Keywords

parameterized computationkernelizationparameterized algorithmNP-hard

References

[1]
R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Springer, London, 2013.
Crossref
[2]
T. Piovesan and S. Kelk, A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), vol. 10, no. 1, pp. 18-25, 2013.
Crossref Google Scholar
[3]
H. Liu and D. Zhu, Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems, Theoretical Computer Science, vol. 498, pp. 115-123, 2013.
Crossref Google Scholar
[4]
N. Betzler, J. Guo, and R. Niedermeier, Parameterized computational complexity of Dodgson and Young elections, Information and Computation, vol. 208, no. 2, pp. 165-177, 2010.
Crossref Google Scholar
[5]
J. Wang, W. Luo, Q. Feng, J. Guo, and J. Chen, Improved linear problem kernel for planar connected dominating set, Theoretical Computer Science, vol. 511, pp. 2-12, 2013.
Crossref Google Scholar
[6]
J. Wang, W. Luo, Q. Feng, and J. Guo, Parameterized complexity of Min-power multicast problems in wireless ad hoc networks, Theoretical Computer Science, vol. 508, pp. 16-25, 2013.
Crossref Google Scholar
[7]
W. Luo, J. Wang, J. Guo, and J. Chen, Parameterized complexity of max-lifetime target coverage in wireless sensor networks, Theoretical Computer Science, vol. 518, pp. 32-41, 2014.
Crossref Google Scholar
[8]
J. Wang, P. Tan, J. Yao, Q. Feng, and J. Chen, On the minimum link-length rectilinear spanning path problem: Complexity and algorithms, IEEE Transactions on Computers, 2014, .
Crossref Google Scholar
[9]
J. Wang, W. Li, S. Li and J. Chen, On the parameterized vertex cover problem for graphs with perfect matching, Science China Information Sciences, vol. 57, pp. 1-12, 2014.
Crossref Google Scholar
[10]
F. Abu-Khzam, M. Fellows, M. A. Langston, and W. H. Suters, Crown structures for vertex cover kernelization, Theory of Computing Systems, vol. 41, pp. 411-430, 2007.
Crossref Google Scholar
[11]
F. Dehne, M. Fellows, F. Rosamond, and P. Shaw, Greedy localization, iterative compression and modeled crown reductions: New FPT techniques and improved algorithms for max set splitting and vertex cover, in Proceedings of the First International Workshop on Parameterized and Exact Computation (IWPEC), vol. 3162 of LNCS, 2004, pp. 271-281.
Crossref
[12]
E. Prieto and C. Sloper, Looking at the stars, Theoretical Computer Science, vol. 351, pp. 437-445, 2006.
Crossref Google Scholar
[13]
J. Wang, D. Ning, Q. Feng, and J. Chen, An improved kernelization for P2-packing, Information Processing Letters, vol. 110, pp. 188-192, 2010.
Crossref Google Scholar
[14]
M. Chlebłka and J. Chlebłkovb, Crown reductions for the minimum weighted vertex cover problem, Discrete Applied Mathematics, vol. 156, pp. 292-312, 2008.
Crossref Google Scholar
[15]
L. Mathieson, E. Prieto, and P. Shaw, Packing edge disjoint triangles: A parameterized view, in Proccedings of the International Workshop on Parametrized and Exact Computation (IWPEC), vol. 3162 of LNCS, 2004, pp. 127-137.
Crossref
[16]
J. Wang, Y. Yang, J. Guo, and J. Chen, Planar graph vertex partition for linear problem kernels, Journal of Computer and System Sciences, vol. 79, no. 5, pp. 609-621, 2013.
Crossref Google Scholar
[17]
Q. Feng, J. Wang, S. Li, and J. Chen, Randomized parameterized algorithms for P2-packing and co-path packing problems, Journal of Combinatorial Optimization, 2014, .
Crossref Google Scholar
[18]
Q. Feng, J. Wang, and J. Chen, Matching and weighted P2-packing: Algorithms and kernels, Theoretical Computer Science, vol. 522, pp. 85-94, 2014.
Crossref Google Scholar
[19]
G. Gutin, E. J. Kim, S. Szeider, and A. Yeo, A probabilistic approach to problems parameterized above or below tight bounds, J. Comput. Syst. Sci., vol. 77, pp. 422-429, 2011.
Crossref Google Scholar
[20]
S. Kratsch and M. Wahlström, Compression via matroids: A randomized polynomial kernel for odd cycle transversal, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 94-103.
Crossref
[21]
J. Chen and S. Lu, Improved parameterized set splitting algorithms: A probabilistic approach, Algorithmica, vol. 54, no. 4, pp. 472-489, 2008.
Crossref Google Scholar
[22]
D. Lokshtanov and C. Sloper, Fixed parameter set splitting, linear kernel and improved running time, in ACiD, volume 4 of Texts in Algorithmics, pp. 105-113, 2005.
[23]
H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin, On problems without polynomial kernels, J. Comput. Syst. Sci., vol. 75, pp. 423-434, 2009.
Crossref Google Scholar
[24]
H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch, Cross-composition: A new technique for kernelization lower bounds, in Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), 2011, pp. 165-176.
[25]
H. L. Bodlaender, S. Thomass, and A. Yeo, Kernel bounds for disjoint cycles and disjoint paths, in Proceedings of the 17th Annual European Symposium on Algorithms (ESA), vol. 5757 of LNCS, 2009, pp. 635-646.
Crossref
[26]
Y. Chen, J. Flum, and M. Mller, Lower bounds for kernelizations and other preprocessing procedures, Theory of Computing Systems, vol. 48, no. 4, pp. 803-839, 2011.
Crossref Google Scholar
[27]
M. Dom, D. Lokshtanov, and S. Saurabh, Incompressibility through colors and IDs, in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), vol. 5555 of LNCS, 2009, pp. 378-389.
Crossref
[28]
H. Fernau, F. V. Fomin, D. Lokshtanov, D. Raible, S. Saurabh, and Y. Villanger, Kernel(s) for problems with no kernel: On outtrees with many leaves, in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS), 2009, pp. 421-432.
[29]
N. Misra, V. Raman, and S. Saurabh, Lower bounds on kernelization, Discrete Optimization, vol. 8, no. 1, pp. 110-128, 2011.
Crossref Google Scholar
[30]
S. Kratsch and M. Wahlström, Two edge modification problems without polynomial kernels, in Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC), vol. 5917 of LNCS, 2009, pp. 264-275.
Crossref
[31]
H. Dell and D. van Melkebeek, Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses, in Proceedings of the 42th Annual ACM Symposium on Theory of Computing (STOC), 2010, pp. 251-260.
Crossref
[32]
S. Kratsch, G. Philip, and S. Ray, Point line cover: The easy kernel is essentially tight, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014, pp. 1596-1606.
Crossref
[33]
H. Dell and D. Marx, Kernelization of packing problems, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 68-81.
Crossref
[34]
H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch, Preprocessing for treewidth: A combinatorial analysis through kernelization, in Proceedings of the 38th International Colloquium Automata, Languages and Programming (ICALP), 2011, pp. 437-448.
Crossref
[35]
F. V. Fomin, D. Lokshtanov, N. Misra, G. Philip, and S. Saurabh, Hitting forbidden minors: Approximation and kernelization, in Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), 2011, pp. 189-200.
[36]
F. Fomin, D. Lokshtanov, S. Saurabh, and D. Thilikos, Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs, in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), 2013, pp. 92-103.
Crossref
[37]
L. Fortnow and R. Santhanam, Infeasibility of instance compression and succinct PCPs for NP, in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 2008, pp. 133-142.
Crossref
[38]
B. M. Jansen and H. L. Bodlaender, Vertex cover kernelization revisited, Theory of Computing Systems, vol. 53, no. 2, pp. 263-299, 2013.
Crossref Google Scholar
[39]
S. Kratsch, Co-nondeterminism in compositions: A kernelization lower bound for a ramsey-type problem, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 114-122.
Crossref
[40]
N. Misra, G. Philip, and V. Raman, The kernelization complexity of connected domination in graphs with (no) small cycles, Algorithmica, vol. 68, no. 2, pp. 504-530, 2014.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 19 Issue 4,
August 2014
Pages 338-345
DOI: 10.1109/TST.2014.6867516
Cite this article:
Feng Q, Zhou Q, Li W, et al. Kernelization in Parameterized Computation: A Survey. Tsinghua Science and Technology, 2014, 19(4): 338-345. https://doi.org/10.1109/TST.2014.6867516

659

Views

20

Downloads

0

Crossref

N/A

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 09 June 2014
Accepted: 17 June 2014
Published: 30 July 2014
© The author(s) 2014
Return