Maximum Independent Sets in Graphs

[This should work with recent desktop versions of Chrome or Firefox, and probably also with other browsers.]
This is an interactive demo of the problem of finding maximum independent sets. Each time you click on below, you'll get a new graph. You can use the three sliders on the right of this button to control the number of vertices and the number of edges. Move your mouse over the sliders to see what exactly they're for. (The other two sliders control the automatic layout of the graph and you probably don't need to worry about them.)
You can drag vertices around if you want to change their position. Their border will then become thicker to indicate that their position is now "fixed", but you can also "unfix" them again by double-clicking them (or by using their context menus, i.e. by right-clicking them).
You can change a randomly created graph in order to create a specific independent set problem: Use the context menu of a vertex to remove it. Use the context menu of the background to add a new vertex. To add or remove an edge, right-click a vertex, select "Add/remove edge", then click another vertex. Alternatively, you can click into the table on the right of the graph to add or remove edges.
You can also use the vertex context menu to add a vertex to an independent set "candidate" (or remove it again). Vertices belonging to the candidate set are shown with an orange background. If two of these orange vertices are connected (i.e. if the set is not an independent set), the edge connecting them will be red. The number at the bottom right counts the members of your candidate set.
Finally, you can click to let the computer find a maximum independent set. On a modern CPU, this shouldn't take more than a second even for the largest graphs this page will allow.

Copyright (c) 2016, Prof. Dr. Edmund Weitz. Impressum, Datenschutzerklärung.