Independent Set 
Maximum set of pairwise nonadjacent vertices in a graph 


p = MixedIntegerLinearProgram(maximization = True)
b = p.new_variable(binary = True)
p.set_objective( sum([b[v] for v in g]) )
for u,v in g.edges(labels = False):
p.add_constraint( b[u] + b[v] <= 1 )
p.solve()
b = p.get_values(b)
print [v for v,i in b.items() if i]

Dominating Set 
Minimum set of vertices whose neighborhood is the whole graph 



Vertex Cover 
Minimum Set of vertices touching each edge 



Partition 
Partition a set of integers into two sets whose sum is equal 



Bipartite Set 
Partition the graph into two independent sets 



Subset Sum 
Find a nonempty subset of integers with null sum 



Distances 
Compute the distance from vertex 0 to any other 



Girth 
Size of the shortest cycle 



Matching 
Maximum number of nonincident edges 



Feedback Arc Set 
Minimum set of arcs hitting all circuits 



Feedback Vertex Set 
Minimum set of vertices hitting all circuits 



Hamiltonian Cycle 
A cycle going through all vertices 



3coloration 
Partition a graph into three independent sets 


