Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Preliminaries Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

30. Kernelization Lower Bounds

verfasst von : Rodney G. Downey, Michael R. Fellows

Erschienen in: Fundamentals of Parameterized Complexity

Verlag: Springer London

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We introduce powerful new techniques to show that FPT parameterized problems do not have polynomial-sized many : 1 kernels, under standard assumptions of classical complexity theory. A new completeness program for exploring the issue for Turing kernelization is also described.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel The M-Hierarchy, and XP-Optimality
Nächstes Kapitel Parameterized Approximation
Fußnoten
1
In the definition below, we have taken the liberty of re-expressing the Harnik–Naor notions in the manner of [83].
 
2
Here, L n =L∩{0,1} n .
 
3
Of course, thinking of this as bitstrings, then we can put all strings representing malformed instances into one equivalence class, but this is a technicality.
 
4
Here size means overall size, whereas the Buss kernel means vertex set size. A vertex size k kernel can have O(k 2) overall size.
 
5
This definition is stated in Kratsch, Philipczuk, Rai, and Raman [469], but was certainly known earlier in classical structural complexity theory.
 
6
The reader should compare this process with that of Lemma 30.10.6.
 
7
This trick was first used by Downey, Fellows, and Regan [256]. There the problem was called Separated t-Normalized Satisfiability.
 
Literatur
15.
83.
H. Bodlaender, R. Downey, M. Fellows, D. Hermelin, On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009) MathSciNetCrossRefMATH
91.
H. Bodlaender, B. Jansen, S. Kratsch, Cross-composition: a new technique for kernelization lower bounds, in Proceedings of 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, Dortmund, Germany, March 10–12, 2011, ed. by T. Schwentick, C. Dürr. Leibniz International Proceedings in Informatics, vol. 9 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, 2011), pp. 165–176
101.
H. 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
114.
H. Buhrman, J. Hitchcock, NP-hard sets are exponentially dense unless coNP ⊆ NP/poly, in Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, College Park, Maryland, USA, June 23–26, 2008 (IEEE Comput. Soc., Los Alamitos, 2008), pp. 1–7 CrossRef
137.
M. Cesati, M.D. Ianni, Computation models for parameterized complexity. Math. Log. Q. 43, 179–202 (1997) CrossRefMATH
140.
J. Chen, H. Fernau, I. Kanj, G. Xia, Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J. Comput. 37(4), 1077–1106 (2007) MathSciNetCrossRefMATH
187.
M. Cygan, F. Fomin, E. van Leeuwin, Parameterized complexity of firefighting revisited, in Parameterized and Exact Computation, 6th International Symposium, IPEC ’11, Revised Selected Papers, Saarbrücken, Germany, September 6–8, 2011, ed. by D. Marx, P. Rossmanith. LNCS, vol. 7112 (Springer, Berlin, 2011), pp. 13–26 CrossRef
188.
M. Cygan, S. Kratsch, M. Pilipczuk, M. Pilipczuk, M. Wahlström, Clique cover and graph separation: new incompressibility results, in ICALP 2012 (2012), pp. 254–265
191.
M. Cygan, M. Pilipczuk, M. Pilipczuk, J.O. Wojtaszczyk, Kernelization hardness of connectivity problems in d-degenerate graphs, in Graph-Theoretic Concepts in Computer Science: 36th International Workshop, WG 2010, Revised Papers, Zarós, Crete, Greece, June 2010 (Springer, Berlin, 2010), pp. 147–158
205.
H. Dell, D. Marx, Kernelization of packing problems, in Proceedings of the Twenty-Third Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012, ed. by Y. Rabani (SIAM, Philadelphia, 2012), pp. 68–81
206.
H. Dell, D. van Melkebeek, Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses, in Proceedings of 42nd ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA, June 6–June 8, 2010, ed. by L. Schulman (ACM, New York, 2010), pp. 251–260 CrossRef
223.
I. Dinur, S. Safra, The importance of being biased, in Proceedings of 34th ACM Symposium on Theory of Computing (STOC ’02), Montréal, Québec, Canada, May 19–May 21, 2002, ed. by J. Reif (ACM, New York, 2002), pp. 33–42
226.
M. Dom, D. Lokshtanov, S. Saurabh, Incompressibility through colors and ids, in Proceedings of 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Part I, Rhodes, Greece, July 5–12, 2009, ed. by S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. Nikoletseas, W. Thomas. LNCS, vol. 5555 (Springer, Berlin, 2009), pp. 378–389 CrossRef
227.
M. Dom, D. Lokshtanov, S. Saurabh, Kernelization lower bounds through colors and IDs, to appear
244.
R. Downey, M. Fellows, Fixed-parameter tractability and completeness II: On completeness for W[1]. Theor. Comput. Sci. 141(1–2), 109–131 (1995) MathSciNetCrossRefMATH
256.
R. Downey, M. Fellows, K. Regan, Parameterized circuit complexity and the W hierarchy. Theor. Comput. Sci. 191(1–2), 97–115 (1998) MathSciNetCrossRefMATH
262.
M. Drescher, A. Vetta, An approximation algorithm for the max leaf spanning arborescence problem. ACM Trans. Algorithms 6(3), 46 (2010) MathSciNetCrossRef
263.
A. Drucker, New limits to classical and quantum instance compression, in FOCS 2012 (2012), pp. 609–618
273.
D. Eppstein, Subgraph isomorphism in planar graphs and related problems, in Proceedings of the Sixth Annual ACM–SIAM Symposium on Discrete Algorithms, San Francisco, California, 22–24 January 1995, ed. by K. Clarkson (SIAM, Philadelphia, 1995), pp. 632–640
274.
P. Erdös, Some remarks on the theory of graphs. Bull. Am. Math. Soc. 53, 292–294 (1947) CrossRefMATH
291.
M. Fellows, D. Hermelin, F. Rosamond, S. Vialette, On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410, 53–61 (2009) MathSciNetCrossRefMATH
306.
H. Fernau, F. 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 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Freiburg, Germany, February 26–28, 2009, ed. by S. Albers, J.-Y. Marion, T. Schwentik. Leibniz International Proceedings in Informatics, vol. 3 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, 2009), pp. 421–432
312.
J. Flum, M. Grohe, Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series (Springer, Berlin, 2006)
313.
J. Flum, M. Grohe, M. Weyer, Bounded fixed-parameter tractability and log2 n nondeterministic bits. J. Comput. Syst. Sci. 72(1), 34–71 (2006) MathSciNetCrossRefMATH
316.
F. Fomin, F. Grandoni, D. Kratsch, Measure and conquer: domination—a case study, in Proceedings of 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), Lisbon, Portugal, July 11–15, 2005, ed. by L. Caires, G. Italiano, L. Monteiro, C. Palamidessi, M. Yung. LNCS, vol. 3580 (Springer, Berlin, 2005), pp. 191–203 CrossRef
320.
F. Fomin, D. Kratsch, G. Woeginger, Exact (exponential) algorithms for the dominating set problem, in Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Revised Papers, Bad Honnef, Germany, June 2004, ed. by J. Hromkovič, M. Nagl, B. Westfechtel. LNCS, vol. 3353 (Springer, Berlin, 2004), pp. 245–256 CrossRef
328.
L. Fortnow, R. Santhanam, Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91–106 (2011). Special issue Celebrating Karp’s Kyoto Prize MathSciNetCrossRefMATH
337.
M. Garey, D. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979) MATH
347.
S. Goldwasser, M. Sipser, Private coins versus public coins in interactive proof systems, in Proceedings of 18th ACM Symposium on Theory of Computing (STOC ’86), Berkeley, California, USA, May 28–May 30, 1986, ed. by J. Hartmanis (1986), pp. 59–68. http://​doi.​acm.​org/​10.​1145/​12130.​12137
353.
J. Gramm, J. Guo, F. Hüffner, R. Niedermeier, Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39(4), 321–347 (2004) MathSciNetCrossRefMATH
355.
J. Gramm, J. Guo, F. Hüffner, R. Niedermeier, Data reduction and exact algorithms for clique cover. ACM J. Exp. Algorithmics 13, 2 (2008)
379.
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, Berkeley, California, USA, 21–24 October 2006 (IEEE Comput. Soc., Los Alamitos, 2006), pp. 719–728 CrossRef
385.
P. Heggernes, P. van’t Hof, B. Lévêque, D. Lokshtanov, C. Paul, Contracting graphs to paths and trees, in Parameterized and Exact Computation, 6th International Symposium, IPEC ’11, Revised Selected Papers, Saarbrücken, Germany, September 6–8, 2011, ed. by D. Marx, P. Rossmanith. LNCS, vol. 7112 (Springer, Berlin, 2011), pp. 55–66 CrossRef
388.
389.
D. Hermelin, X. Wu, Weak compositions and their applications to polynomial lower bounds for kernelization. Electron. Colloq. Comput. Complex. 18, 72 (2011)
439.
S. Khot, V. Raman, Parameterized complexity of finding subgraphs with hereditary properties. Theor. Comput. Sci. 289(2), 997–1008 (2002) MathSciNetCrossRefMATH
445.
D. Kirkpatrick, P. Hell, On the completeness of the generalized matching problem, in Proceedings of 10th ACM Symposium on Theory of Computing (STOC ’78), San Diego, California, USA, May 1–May 3, 1978, ed. by R. Lipton, W. Burkhard, W. Savitch, E. Friedman, A. Aho (ACM, New York, 1978), pp. 240–245
447.
H. Klauck, A. Nayak, A. Ta-Shma, D. Zuckerman, Interaction in quantum communication. IEEE Trans. Inf. Theory 53(6), 1970–1982 (2007) MathSciNetCrossRef
468.
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, Kyoto, Japan, January 17–19, 2012, ed. by Y. Rabani (SIAM, Philadelphia, 2012), pp. 114–122
469.
S. Kratsch, M. Philipczuk, A. Rai, V. Raman, Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs, in Algorithm Theory—SWAT 2012 (Springer, Berlin, 2012), pp. 364–375
546.
R. Niedermeier, Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, vol. 31 (Oxford University Press, Oxford, 2006) CrossRefMATH
556.
A. Pavan, A. Selman, S. Sengupta, V. Variyam, Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy. Theor. Comput. Sci. 385(1–3), 167–178 (2007) CrossRefMATH
573.
598.
A. Sahai, S.P. Vadhan, A complete problem for statistical zero knowledge. J. ACM 50(2), 196–249 (2003) MathSciNet
671.
R. Yuster, Combinatorial and computational aspects of graph packing and graph decomposition. Comput. Sci. Rev. 1, 12–26 (2007) CrossRef
Metadaten
Titel
Kernelization Lower Bounds
verfasst von
Rodney G. Downey
Michael R. Fellows
Copyright-Jahr
2013
Verlag
Springer London
Buch
Fundamentals of Parameterized Complexity

Print ISBN: 978-1-4471-5558-4

Electronic ISBN: 978-1-4471-5559-1

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4471-5559-1_30