Counting Answers to Existential Questions
From MaRDI portal
Publication:5091275
DOI10.4230/LIPIcs.ICALP.2019.113OpenAlexW2965645196MaRDI QIDQ5091275
Holger Dell, Marc Roth, Philip Wellnitz
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1902.04960
graph homomorphismsparameterized complexityconjunctive queriescounting complexityfine-grained complexity
Related Items
Counting Small Induced Subgraphs Satisfying Monotone Properties, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, Answer Counting under Guarded TGDs, Solving projected model counting by utilizing treewidth and its limits, Parameterized Counting and Cayley Graph Expanders, Parameterized counting of partially injective homomorphisms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Structural tractability of counting of solutions to conjunctive queries
- Fundamentals of parameterized complexity
- Tractable counting of the answers to conjunctive queries
- Faster algorithms for finding and counting subgraphs
- The complexity of counting homomorphisms seen from the other side
- Highly connected sets and the excluded grid theorem
- Conjunctive query containment revisited
- Parametrized complexity theory.
- Finding, Minimizing, and Counting Weighted Subgraphs
- Counting and Detecting Small Subgraphs via Equations
- PP is as Hard as the Polynomial-Time Hierarchy
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- On conjunctive queries containing inequalities
- Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
- Faster decision of first-order graph properties
- The Parameterized Complexity of Counting Problems
- Homomorphisms are a good basis for counting small subgraphs
- Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
- When is the evaluation of conjunctive queries tractable?
- Operations with structures
- [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]
- A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
- On the complexity of \(k\)-SAT
