Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds.
Jacob FockeDániel MarxPawel RzazewskiPublished in: CoRR (2021)
Keyphrases
- bounded treewidth
- conjunctive queries
- tight complexity bounds
- np complete
- monadic datalog
- query answering
- decision procedures
- query evaluation
- integrity constraints
- data complexity
- decision problems
- datalog programs
- query language
- data exchange
- boolean functions
- special case
- query rewriting
- dl lite
- graph theory
- computational complexity
- database
- constraint satisfaction problems
- relational learning
- satisfiability problem
- data integration