Complexity Explorer Santa Few Institute

Computation in Complex Systems (Spring 2022)

Lead instructor:

This course is no longer in session.

2.2 Dynamic Programming » Max Weight Independent Set interactive

Max Weight Independent Set

Try out solutions to find the max weight independent set in a different graph.


Exploring the model

  • The numbers of each node indicate its weight. The goal is to maximize the weight of the independent set. 

  • Click on nodes in the graph to select them as members of the set. The chosen nodes will appear to the right, as members of the independent set. The weight of the independent set appears at the top.

  • When nodes are selected as members of the independent set, they turn green. White nodes can be selected; they are not connected to any selected nodes and thus maintain the independence of the set. Pink nodes are connected to nodes in the set and thus can not become members of the set without violating its independence.

  • Click the "restart" button in the upper left to re-set the graph.