Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds.
Jacob FockeDániel MarxPawel RzazewskiPublished in: SODA (2022)
Keyphrases
- bounded treewidth
- conjunctive queries
- tight complexity bounds
- np complete
- monadic datalog
- query answering
- integrity constraints
- data complexity
- decision procedures
- decision problems
- query evaluation
- data exchange
- boolean functions
- graph theory
- special case
- query language
- relational learning
- query rewriting
- datalog programs
- description logics
- dl lite
- np hard
- probability distribution
- artificial intelligence
- data warehouse