What are the Least Tractable Instances of max Independent Set?

David S. Johnson Mario Szegedy

Published in: SODA (1999)

Keyphrases

independent set
np complete
computational complexity
randomly generated
maximum weight
maximum independent set
learning algorithm
np hard
graphical models
special case
random walk
tractable classes