Document Open Access Logo

Counting Answers to Existential Questions (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Holger Dell , Marc Roth , Philip Wellnitz

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.113.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Holger Dell
  • Cluster of Excellence (MMCI), Saarland Informatics Campus (SIC), Saarbrücken, Germany
Marc Roth
  • Cluster of Excellence (MMCI), Saarland Informatics Campus (SIC), Saarbrücken, Germany
Philip Wellnitz
  • Max Planck Institute for Informatics, Saarland Informatics Campus (SIC), Saarbrücken, Germany

Funding

  • Wellnitz, Philip: Partially funded by the Saarbrücken Graduate School of Computer Science.

Acknowledgements

We thank Cornelius Brand, Karl Bringmann, Radu Curticapean, Reinhard Diestel, Joshua Erde, Stephan Kreutzer, Stefan Mengel, Daniel Weißauer, and an anonymous reviewer for discussions and advice.

Cite As Get BibTex

Holger Dell, Marc Roth, and Philip Wellnitz. Counting Answers to Existential Questions (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 113:1-113:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.113

Abstract

Conjunctive queries select and are expected to return certain tuples from a relational database. We study the potentially easier problem of counting all selected tuples, rather than enumerating them. In particular, we are interested in the problem’s parameterized and data complexity, where the query is considered to be small or even fixed, and the database is considered to be large. We identify two structural parameters for conjunctive queries that capture their inherent complexity: The dominating star size and the linked matching number. If the dominating star size of a conjunctive query is large, then we show that counting solution tuples to the query is at least as hard as counting dominating sets, which yields a fine-grained complexity lower bound under the Strong Exponential Time Hypothesis (SETH) as well as a #W[2]-hardness result in parameterized complexity. Moreover, if the linked matching number of a conjunctive query is large, then we show that the structure of the query is so rich that arbitrary queries up to a certain size can be encoded into it; in the language of parameterized complexity, this essentially establishes a #A[2]-completeness result.
Using ideas stemming from Lovász (1967), we lift complexity results from the class of conjunctive queries to arbitrary existential or universal formulas that might contain inequalities and negations on constraints over the free variables. As a consequence, we obtain a complexity classification that refines and generalizes previous results of Chen, Durand, and Mengel (ToCS 2015; ICDT 2015; PODS 2016) for conjunctive queries and of Curticapean and Marx (FOCS 2014) for the subgraph counting problem. Our proof also relies on graph minors, and we show a strengthening of the Excluded-Grid-Theorem which might be of independent interest: If the linked matching number (and thus the treewidth) is large, then not only can we find a large grid somewhere in the graph, but we can find a large grid whose diagonal has disjoint paths leading into an assumed node-well-linked set.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Conjunctive queries
  • graph homomorphisms
  • counting complexity
  • parameterized complexity
  • fine-grained complexity

Metrics

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

Related Versions

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/.
  2. Ashok K. Chandra and Philip M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 77-90, 1977. URL: http://dx.doi.org/10.1145/800105.803397.
  3. Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. Theoretical Computer Science, 239(2):211-229, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(99)00220-0.
  4. Hubie Chen and Stefan Mengel. A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries. In 18th International Conference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium, pages 110-126, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.ICDT.2015.110.
  5. Hubie Chen and Stefan Mengel. Counting Answers to Existential Positive Queries: A Complexity Classification. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 315-326, 2016. URL: http://dx.doi.org/10.1145/2902251.2902279.
  6. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th ACM Symposium on Theory of Computing, STOC, pages 210-223, 2017. URL: http://dx.doi.org/10.1145/3055399.3055502.
  7. Radu Curticapean and Dániel Marx. Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 130-139, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.22.
  8. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theoretical Computer Science, 329(1):315-323, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2004.08.008.
  9. Víctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics. In Pascal Van Hentenryck, editor, Principles and Practice of Constraint Programming - CP 2002, 8th International Conference, CP 2002, Ithaca, NY, USA, September 9-13, 2002, Proceedings, volume 2470 of Lecture Notes in Computer Science, pages 310-326. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-46135-3_21.
  10. Reinhard Diestel, Tommy R. Jensen, Konstantin Yu. Gorbunov, and Carsten Thomassen. Highly Connected Sets and the Excluded Grid Theorem. Journal of Combinatorial Theory, Series B, 75(1):61-73, 1999. URL: http://dx.doi.org/10.1006/jctb.1998.1862.
  11. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  12. Arnaud Durand and Stefan Mengel. Structural Tractability of Counting of Solutions to Conjunctive Queries. Theory of Computing Systems, 57(4):1202-1249, 2015. URL: http://dx.doi.org/10.1007/s00224-014-9543-y.
  13. Jörg Flum and Martin Grohe. The Parameterized Complexity of Counting Problems. SIAM Journal of Computing, 33(4):892-922, 2004. URL: http://dx.doi.org/10.1137/S0097539703427203.
  14. Jörg Flum and Martin Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006. URL: http://dx.doi.org/10.1007/3-540-29953-X.
  15. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, and B. V. Raghavendra Rao. Faster algorithms for finding and counting subgraphs. jcss, 78(3):698-706, 2012. URL: http://dx.doi.org/10.1016/j.jcss.2011.10.001.
  16. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2162-2181, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.141.
  17. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1):1, 2007. URL: http://dx.doi.org/10.1145/1206035.1206036.
  18. Martin Grohe, Thomas Schwentick, and Luc Segoufin. When is the evaluation of conjunctive queries tractable? In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 657-666, 2001. URL: http://dx.doi.org/10.1145/380752.380867.
  19. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  20. Anthony C. Klug. On conjunctive queries containing inequalities. Journal of the ACM, 35(1):146-160, 1988. URL: http://dx.doi.org/10.1145/42267.42273.
  21. Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Counting and Detecting Small Subgraphs via Equations. SIAM Journal on Discrete Mathematics, 27(2):892-909, 2013. URL: http://dx.doi.org/10.1137/110859798.
  22. László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321-328, 1967. Google Scholar
  23. László Lovász. Large networks and graph limits, volume 60. American Mathematical Society Providence, 2012. Google Scholar
  24. Dániel Marx. Can You Beat Treewidth? Theory of Computing, 6(1):85-112, 2010. URL: http://dx.doi.org/10.4086/toc.2010.v006a005.
  25. Stefan Mengel. Conjunctive queries, arithmetic circuits and counting complexity. PhD thesis, University of Paderborn, 2013. URL: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-11944.
  26. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  27. Reinhard Pichler and Sebastian Skritek. Tractable counting of the answers to conjunctive queries. Journal of Computer and System Sciences, 79(6):984-1001, 2013. URL: http://dx.doi.org/10.1016/j.jcss.2013.01.012.
  28. Mihai Pătraşcu and Ryan Williams. On the Possibility of Faster SAT Algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1065-1075, 2010. URL: http://dx.doi.org/10.1137/1.9781611973075.86.
  29. Gian-Carlo Rota. On the foundations of combinatorial theory I. Theory of Möbius functions. Probability theory and related fields, 2(4):340-368, 1964. Google Scholar
  30. Marc Roth. Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pages 63:1-63:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2017.63.
  31. Seinosuke Toda. PP is as Hard as the Polynomial-Time Hierarchy. SIAM J. Comput., 20(5):865-877, 1991. URL: http://dx.doi.org/10.1137/0220053.
  32. Ryan Williams. Faster decision of first-order graph properties. In Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, Vienna, Austria, July 14 - 18, 2014, pages 80:1-80:6, 2014. URL: http://dx.doi.org/10.1145/2603088.2603121.
  33. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM Journal of Computing, 42(3):831-854, 2013. URL: http://dx.doi.org/10.1137/09076619X.
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 About DROPS Imprint Privacy Contact