Inapproximability of Treewidth and Related Problems (Extended Abstract).
Yu WuPer AustrinToniann PitassiDavid LiuPublished in: IJCAI (2015)
Keyphrases
- related problems
- extended abstract
- approximation algorithms
- upper bound
- search space
- space complexity
- bounded treewidth
- boolean functions
- discrete random variables
- broadly applicable
- tree decompositions
- range searching
- machine learning
- special case
- lower bound
- integrity constraints
- database
- np complete
- logic programs
- stable marriage