×

zbMATH — the first resource for mathematics

On problems without polynomial kernels. (English) Zbl 1192.68288
Summary: Kernelization is a strong and widely-applied technique in parameterized complexity. A kernelization algorithm, or simply a kernel, is a polynomial-time transformation that transforms any given parameterized instance to an equivalent instance of the same problem, with size and parameter bounded by a function of the parameter in the input. A kernel is polynomial if the size and parameter of the output are polynomially-bounded by the parameter of the input.
In this paper, we develop a framework which allows showing that a wide range of FPT problems do not have polynomial kernels. Our evidence relies on hypothesis made in the classical world (i.e., non-parametric complexity), and revolves around a new type of algorithm for classical decision problems, called a distillation algorithm, which is of independent interest. Using the notion of distillation algorithms, we develop a generic lower-bound engine that allows us to show that a variety of FPT problems, fulfilling certain criteria, cannot have polynomial kernels unless the polynomial hierarchy collapses. These problems include \(k\)-Path, \(k\)-Cycle, \(k\)-Exact Cycle, \(k\)-Short Cheap Tour, \(k\)-Graph Minor Order Test, \(k\)-Cutwidth, \(k\)-Search Number, \(k\)-Pathwidth, \(k\)-Treewidth, \(k\)-Branchwidth, and several optimization problems parameterized by treewidth and other structural parameters.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alber, J.; Fellows, M.R.; Niedermeier, R., Polynomial-time data reduction for dominating set, J. ACM, 51, 3, 363-384, (2004) · Zbl 1192.68337
[2] Alon, N.; Yuster, R.; Zwick, U., Color coding, J. ACM, 42, 4, 844-856, (1995) · Zbl 0885.68116
[3] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability. A survey, Bit, 25, 1, 2-23, (1985) · Zbl 0573.68018
[4] Bar-Yehuda, R.; Even, S., A local-ratio theorem for approximating the weighted vertex cover problem, (), 27-46 · Zbl 0557.90072
[5] Bodlaender, H.L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. comput., 25, 1305-1317, (1996) · Zbl 0864.68074
[6] Bodlaender, H.L., A partial k-arboretum of graphs with bounded treewidth, Theoret. comput. sci., 209, 1-2, 1-45, (1998) · Zbl 0912.68148
[7] H.L. Bodlaender, A cubic kernel for feedback vertex set, in: Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2007, pp. 320-331 · Zbl 1186.68217
[8] H.L. Bodlaender, S. Thomassé, A. Yeo, Analysis of data reduction: Transformations give evidence for non-existence of polynomial kernels, Technical Report UU-CS-2008-030, Department of Information and Computing Sciences, Utrecht University, 2008
[9] P.S. Bonsma, T. Brüggemann, G.J. Woeginger, A faster FPT algorithm for finding spanning trees with many leaves, in: Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2003, pp. 259-268 · Zbl 1124.68398
[10] H. Buhrman, private communication, 2007
[11] K. Burrage, V. Estivill-Castro, M.R. Fellows, M.A. Langston, S. Mac, F.A. Rosamond, The undirected feedback vertex set problem has a Poly(k) kernel, in: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC), 2006, pp. 192-202 · Zbl 1154.68421
[12] Cai, L.; Chen, J.; Downey, R.G.; Fellows, M.R., Advice classes of parameterized tractability, Ann. pure appl. logic, 84, 1, 119-138, (1997) · Zbl 0873.68071
[13] L. Cai, D.W. Juedes, Subexponential parameterized algorithms collapse the W-hierarchy, in: Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP), 2001, pp. 273-284 · Zbl 0986.68038
[14] Cesati, M.; Di Ianni, M., Computation models for parameterized complexity, MLQ math. log. Q., 43, 179-202, (1997) · Zbl 0870.68063
[15] J. Chen, B. Chor, M. Fellows, X. Huang, D.W. Juedes, I. Kanj, G. Xia, Tight lower bounds for certain parameterized NP-hard problems, in: Proc. of the 19th Annual IEEE Conference on Computational Complexity (CCC), 2004, pp. 150-160 · Zbl 1161.68476
[16] J. Chen, H. Fernau, I.A. Kanj, G. Xia, Parametric duality and kernelization: Lower bounds and upper bounds on kernel size, in: Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2005, pp. 269-280 · Zbl 1118.68506
[17] J. Chen, X. Huang, I.A. Kanj, G. Xia, Linear FPT reductions and computational lower bounds, in: Proc. of the 36th Annual ACM Symposium on Theory of Computing (STOC), 2004, pp. 212-221 · Zbl 1192.68313
[18] Y. Chen, J. Flum, M. Müller, Lower bounds for kernelizations, manuscript, 2007
[19] Y. Chen, M. Müller, The price of one sided gaps, manuscript, 2008
[20] S.A. Cook, The complexity of theorem-proving procedures, in: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), 1971, pp. 151-158
[21] I. Dinur, S. Safra, The importance of being biased, in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 33-42 · Zbl 1192.68318
[22] R.G. Downey, Parameterized complexity for the skeptic, in: Proceedings of the 18th IEEE Annual Conference on Computational Complexity, 2003, pp. 147-170
[23] Downey, R.G.; Estivill-Castro, V.; Fellows, M.R.; Prieto, E.; Rosamond, F.A., Cutting up is hard to do: the parameterized complexity of k-cut and related problems, () · Zbl 1270.68112
[24] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer-Verlag · Zbl 0914.68076
[25] D. Eppstein, Subgraph isomorphism in planar graphs and related problems, in: Proceedings of the 6th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA), 1995, pp. 632-640 · Zbl 0858.05075
[26] V. Estivill-Castro, M. Fellows, M. Langston, F. Rosemond, FPT is P-time extremal structure I, in: Proc. of the 1st Workshop on Algorithms and Complexity in Durham (ACiD), 2005, pp. 1-41
[27] Fellows, M.R.; Langston, M.A., Nonconstructive proofs of polynomial-time complexity, Inform. process. lett., 26, 157-162, (1988) · Zbl 0637.68053
[28] Fellows, M.R.; Langston, M.A., On well-partial-order theory and its application to combinatorial problems of VLSI design, SIAM J. discrete math., 5, 1, 117-126, (1992) · Zbl 0739.68042
[29] M.R. Fellows, F. Rosamond, Why is P not equal to NP? in: Proceedings of the 3rd Conference on Computability in Europe (CiE), 2007, pp. 151-160
[30] H. Fernau, Parameterized algorithms: A graph-theoretic approach, PhD thesis, 2005
[31] H. Fernau, F.V. Fomin, D. Lokshtanov, D. Raible, S. Saurabh, Y. Villanger, Kernel(s) for problems with no kernel: On out-trees with many leaves, in: Proceedings of the 26th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2009, pp. 421-432 · Zbl 1236.68087
[32] Flum, J.; Grohe, M., Parameterized complexity theory, (2006), Springer-Verlag
[33] J. Flum, M. Grohe, M. Weyer, Bounded fixed-parameter tractability and \(\log^2 n\) nondeterministic bits, in: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004, pp. 555-567 · Zbl 1099.68642
[34] F.V. Fomin, D.M. Thilikos, Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up, in: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004, pp. 581-592 · Zbl 1099.68077
[35] L. Fortnow, R. Santhanam, Infeasibility of instance compression and succinct PCPs for NP, in: Proceedings of the 40th Annual Symposium on the Theory of Computing (STOC), 2008, pp. 133-142 · Zbl 1231.68133
[36] Frick, M.; Grohe, M., The complexity of first-order and monadic second-order logic revisited, Ann. pure appl. logic, 130, 1-3, 3-31, (2004) · Zbl 1062.03032
[37] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039
[38] Gramm, J.; Guo, J.; Huffner, F.; Niedermeier, R., Graph-modeled data clustering: exact algorithms for clique generation, Math. syst. theory, 38, 373-392, (2005) · Zbl 1084.68117
[39] Guo, J.; Niedermeier, R., Fixed-parameter tractability and data reduction for multicut in trees, Networks, 46, 3, 124-135, (2005) · Zbl 1081.68070
[40] Guo, J.; Niedermeier, R., Invitation to data reduction and problem kernelization, SIGACT news, 38, 1, 31-45, (2007)
[41] J. Guo, R. Niedermeier, Linear problem kernels for NP-hard problems on planar graphs, in: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), 2007, pp. 375-386 · Zbl 1171.68488
[42] J. Guo, R. Niedermeier, S. Wernicke, Parameterized complexity of generalized vertex cover problems, in: Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS), 2005, pp. 36-48 · Zbl 1161.68669
[43] D. Harnik, M. Naor, On the compressibility of NP instances and cryptographic applications, in: Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 719-728
[44] Hochbaum, D.S., Efficient bounds for the stable set, vertex cover and set packing problems, Discrete appl. math., 6, 243-254, (1983) · Zbl 0523.05055
[45] J. Kneis, D. Mölle, S. Richter, P. Rossmanith, Divide-and-color, in: Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2006, pp. 58-67 · Zbl 1167.68411
[46] Ko, K., On self-reducibility and weak P-selectivity, J. comput. system sci., 26, 2, 209-221, (1983) · Zbl 0519.68062
[47] Ladner, R., On the structure of polynomial time reducibility, J. ACM, 22, 1, 155-171, (1975) · Zbl 0322.68028
[48] Y. Liu, S. Lu, J. Chen, S. Sze, Greedy localization and color-coding: Improved matching and packing algorithms, in: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC), 2006, pp. 84-95 · Zbl 1154.68429
[49] Nemhauser, G.L.; Trotter, L.E., Vertex packings: structural properties and algorithms, Math. program., 8, 232-248, (1975) · Zbl 0314.90059
[50] Niedermeier, R.; Rossmanith, P., An efficient fixed-parameter algorithm for 3-hitting set, J. discrete algorithms, 1, 89-102, (2003) · Zbl 1118.68511
[51] J. Plehn, B. Voigt, Finding minimally weighted subgraphs, in: Proceedings of the 16th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 1990, pp. 18-29 · Zbl 0768.68170
[52] N. Robertson, D.P. Sanders, P. Seymour, R. Thomas, Efficiently four-coloring planar graphs, in: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC), 1996, pp. 571-575 · Zbl 0917.05030
[53] Stockmeyer, L.J., The polynomial-time hierarchy, Theoret. comput. sci., 3, 1-22, (1977) · Zbl 0353.02024
[54] S. Thomassé, A quadratic kernel for feedback vertex set, in: Proceedings of the 20th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA), 2009, pp. 115-119
[55] K. Weihe, Covering trains by stations or the power of data reduction, in: Proceedings of the 1st ACM/SIAM Workshop on ALgorithm ENgineering and EXperiments (ALENEX), 1998, pp. 1-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.