Structural solutions to maximum independent set and related problems