Document Open Access Logo

Lower Bounds for Conjunctive and Disjunctive Turing Kernels

Authors Elisabet Burjons , Peter Rossmanith

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.12.pdf
  • Filesize: 0.76 MB
  • 17 pages

Document Identifiers

Author Details

Elisabet Burjons
  • Department of Computer Science, RWTH Aachen, Germany
Peter Rossmanith
  • Department of Computer Science, RWTH Aachen, Germany

Funding

  • Burjons, Elisabet: This work was supported by the Swiss National Science Foundation postdoc mobility grant P2EZP2-191861.

Cite AsGet BibTex

Elisabet Burjons and Peter Rossmanith. Lower Bounds for Conjunctive and Disjunctive Turing Kernels. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.12

Abstract

The non-existence of polynomial kernels for OR- and AND-compositional problems is now a well-established result. Some of these problems have adaptive or non-adaptive polynomial Turing kernels. Up to now, most known polynomial Turing kernels are non-adaptive and most of them are of the conjunctive or disjunctive kind. For some problems it has been conjectured that the existence of polynomial Turing kernels is unlikely. For instance, either all or none of the WK[1]-complete problems have polynomial Turing kernels. While it has been conjectured that they do not, a proof tying their non-existence to some complexity theoretic assumption is still missing and seems to be beyond the reach of today’s standard techniques. In this paper, we prove that OR-compositional problems and all WK[1]-hard problems do not have conjunctive polynomial kernels, a special type of non-adaptive Turing kernels, under the assumption that coNP ⊈ NP/poly. Similarly, it is unlikely that AND-compositional problems have disjunctive polynomial kernels. Moreover, we present a way to prove that the parameterized versions of some ⊕ P-hard problems, for instance, Odd Path on planar graphs, do not have conjunctive or disjunctive polynomial kernels, unless coNP ⊆ NP/poly. Finally, we identify a problem that is unlikely to have either a conjunctive or disjunctive polynomial kernel, unless coNP ⊆ NP/poly, due to a reduction from an NP-hard problem instead: Weighted Odd Path on planar graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized Complexity
  • Turing kernels

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Daniel Binkele-Raible, Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Kernel(s) for problems with no kernel: On out-trees with many leaves. ACM Trans. Algorithms, 8(4):38:1-38:19, 2012. URL: https://doi.org/10.1145/2344422.2344428.
  2. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. URL: https://doi.org/10.1016/j.jcss.2009.04.001.
  3. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discret. Math., 28(1):277-305, 2014. URL: https://doi.org/10.1137/120880240.
  4. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci., 412(35):4570-4578, 2011. URL: https://doi.org/10.1016/j.tcs.2011.04.039.
  5. L. Bodlaender, Hans, Erik D. Demaine, Michael R. Fellows, Jiong Guo, Danny Hermelin, Daniel Lokshtanov, Moritz Müller, Venkatesh Raman, Johan van Rooij, and Frances A. Rosamond. Open problems in parameterized and exact computation - IWPEC 2008. Technical Report UU-CS-2008-017, Dept. of Informatics and Computing Sciences, Utrecht University, 2008. Google Scholar
  6. Radu Curticapean, Holger Dell, and Thore Husfeldt. Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1-34:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.34.
  7. Marek Cygan, Marcin Pilipczuk, and Michal Pilipczuk. Known algorithms for edge clique cover are probably optimal. SIAM J. Comput., 45(1):67-83, 2016. URL: https://doi.org/10.1137/130947076.
  8. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization lower bounds through colors and ids. ACM Trans. Algorithms, 11(2):13:1-13:20, 2014. URL: https://doi.org/10.1145/2650261.
  9. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  10. Andrew Drucker. New limits to classical and quantum instance compression. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 609-618. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.71.
  11. Andrew Drucker. New limits to classical and quantum instance compression. SIAM J. Comput., 44(5):1443-1479, 2015. URL: https://doi.org/10.1137/130927115.
  12. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. URL: https://doi.org/10.1017/9781107415157.
  13. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.007.
  14. Danny Hermelin, Stefan Kratsch, Karolina Soltys, Magnus Wahlström, and Xi Wu. A completeness theory for polynomial (Turing) kernelization. Algorithmica, 71(3):702-730, 2015. URL: https://doi.org/10.1007/s00453-014-9910-8.
  15. Bart M. P. Jansen. Turing kernelization for finding long paths and cycles in restricted graph classes. J. Comput. Syst. Sci., 85:18-37, 2017. URL: https://doi.org/10.1016/j.jcss.2016.10.008.
  16. Johannes Köbler and Osamu Watanabe. New collapse consequences of NP having small circuits. In Zoltán Fülöp and Ferenc Gécseg, editors, Automata, Languages and Programming, 22nd International Colloquium, ICALP95, Szeged, Hungary, July 10-14, 1995, Proceedings, volume 944 of Lecture Notes in Computer Science, pages 196-207. Springer, 1995. URL: https://doi.org/10.1007/3-540-60084-1_74.
  17. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Comb., 7(1):105-113, 1987. URL: https://doi.org/10.1007/BF02579206.
  18. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  19. Christos H. Papadimitriou and Stathis Zachos. Two remarks on the power of counting. In Armin B. Cremers and Hans-Peter Kriegel, editors, Theoretical Computer Science, 6th GI-Conference, Dortmund, Germany, January 5-7, 1983, Proceedings, volume 145 of Lecture Notes in Computer Science, pages 269-276. Springer, 1983. URL: https://doi.org/10.1007/BFb0009651.
  20. Amit Sahai and Salil P. Vadhan. A complete problem for statistical zero knowledge. J. ACM, 50(2):196-249, 2003. URL: https://doi.org/10.1145/636865.636868.
  21. Uwe Schöning. Probabilistic complexity classes and lowness. J. Comput. Syst. Sci., 39(1):84-100, 1989. URL: https://doi.org/10.1016/0022-0000(89)90020-2.
  22. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991. URL: https://doi.org/10.1137/0220053.
  23. Leslie G. Valiant. Completeness for parity problems. In Lusheng Wang, editor, Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 1-8. Springer, 2005. URL: https://doi.org/10.1007/11533719_1.
  24. Jouke Witteveen, Ralph Bottesch, and Leen Torenvliet. A hierarchy of polynomial kernels. In Barbara Catania, Rastislav Královic, Jerzy R. Nawrocki, and Giovanni Pighizzini, editors, SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 27-30, 2019, Proceedings, volume 11376 of Lecture Notes in Computer Science, pages 504-518. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-10801-4_39.
  25. Chee-Keng Yap. Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci., 26:287-300, 1983. URL: https://doi.org/10.1016/0304-3975(83)90020-8.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact