A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time.
Vincent Cohen-AddadTobias MömkeVictor VerdugoPublished in: IPCO (2022)
Keyphrases
- bounded treewidth
- fixed parameter tractable
- integrality gap
- np complete
- linear programming relaxation
- highly parallelizable
- conjunctive queries
- approximation algorithms
- computational problems
- decision problems
- lower bound
- boolean functions
- np hard
- relational learning
- machine learning
- query language
- reinforcement learning