Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs.
Euiwoong LeePasin ManurangsiPublished in: ITCS (2024)
Keyphrases
- independent set
- max csp
- bounded degree
- maximum independent set
- graph theoretic
- arc consistency
- constraint satisfaction
- maximum weight
- constraint networks
- bounded treewidth
- constraint satisfaction problems
- constraint programming
- bipartite graph
- machine learning
- heuristic search
- optimisation problems
- np complete
- information extraction
- learning algorithm