Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs.
Jacob FockeDániel MarxFionn Mc InerneyDaniel NeuenGovind S. SankarPhilipp SchepperPhilip WellnitzPublished in: SODA (2023)
Keyphrases
- bounded treewidth
- conjunctive queries
- tight complexity bounds
- np complete
- monadic datalog
- query answering
- decision procedures
- query evaluation
- integrity constraints
- decision problems
- data complexity
- query language
- boolean functions
- datalog programs
- query rewriting
- dl lite
- special case
- bounded degree
- data exchange
- databases
- description logics
- expert systems
- natural language