Open Access
Issue
Published:
30 July 2014
Kernelization in Parameterized Computation: A Survey
Jianxin Wang(
)
)
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
Download citation
462
Views
16
Downloads
Citations
0
Crossref
N/A
WoS
0
Scopus
0
CSCD
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.
menu
Abstract
Full text
Outline
About this article
Kernelization in Parameterized Computation: A Survey
Jianxin Wang(
)
)
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 computation, kernelization, parameterized algorithm, NP-hard
References(40)
[1]
R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Springer, London, 2013.
[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.
[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.
[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.
[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.
[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.
[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.
[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, .
[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.
[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.
[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.
[12]
E. Prieto and C. Sloper, Looking at the stars, Theoretical Computer Science, vol. 351, pp. 437-445, 2006.
[13]
J. Wang, D. Ning, Q. Feng, and J. Chen, An improved kernelization for P 2
[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.
[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.
[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.
[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, .
[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.
[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.
[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.
[21]
J. Chen and S. Lu, Improved parameterized set splitting algorithms: A probabilistic approach, Algorithmica, vol. 54, no. 4, pp. 472-489, 2008.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[38]
B. M. Jansen and H. L. Bodlaender, Vertex cover kernelization revisited, Theory of Computing Systems, vol. 53, no. 2, pp. 263-299, 2013.
[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.
[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.
Publication history
Copyright
Acknowledgements
Rights and permissions
Publication history
Received: 09 June 2014
Accepted: 17 June 2014
Published:
30 July 2014
Issue date: August 2014
Copyright
© The author(s) 2014
Acknowledgements
This work was supported by the National Natural Science Foundation of China (Nos. 61173051, 61103033, and 61232001).
FEEDBACK 
TOP