Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs.

Euiwoong Lee Pasin Manurangsi

Published in: CoRR (2023)

Keyphrases

independent set
max csp
bounded degree
maximum independent set
graph theoretic
constraint satisfaction
phase transition
maximum weight
computational complexity
optimisation problems
arc consistency
constraint networks
bounded treewidth
np complete
dynamic programming
np hard
learning algorithm