2026-07-24T02:00:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18179 2024-03-06T11:01:14Z ddc:004 open_access

The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems Fan, Austen Z. Koutris, Paraschos Zhao, Hangdong Fine-grained complexity conjunctive queries semiring-oblivious reduction We study the fine-grained complexity of evaluating Boolean Conjunctive Queries and their generalization to sum-of-product problems over an arbitrary semiring. For these problems, we present a general semiring-oblivious reduction from the k-clique problem to any query structure (hypergraph). Our reduction uses the notion of embedding a graph to a hypergraph, first introduced by Marx [Dániel Marx, 2013]. As a consequence of our reduction, we can show tight conditional lower bounds for many classes of hypergraphs, including cycles, Loomis-Whitney joins, some bipartite graphs, and chordal graphs. These lower bounds have a dependence on what we call the clique embedding power of a hypergraph H, which we believe is a quantity of independent interest. We show that the clique embedding power is always less than the submodular width of the hypergraph, and present a decidable algorithm for computing it. We conclude with many open problems for future research. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Austen Z. Fan and Paraschos Koutris and Hangdong Zhao 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.127 urn:nbn:de:0030-drops-181791 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.127 eng https://creativecommons.org/licenses/by/4.0/legalcode