List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs.
Baris Can EsmerJacob FockeDániel MarxPawel RzazewskiPublished in: CoRR (2022)
Keyphrases
- bounded treewidth
- conjunctive queries
- tight complexity bounds
- weighted graph
- np complete
- undirected graph
- query answering
- decision procedures
- edge weights
- query evaluation
- vertex set
- integrity constraints
- data complexity
- decision problems
- graph theory
- query language
- directed graph
- spanning tree
- directed acyclic graph
- boolean functions
- relational learning
- data exchange
- random graphs
- bounded degree
- dl lite
- objective function
- datalog programs
- query rewriting
- databases
- satisfiability problem
- state space
- expressive power