Lesson 3

The \(\texttt{networkx}\) library has a built-in function for approximate finding of a maximum clique and a maximum independent set in a graph.

import networkx as nx
from networkx.algorithms.approximation import ramsey_R2
from itertools import combinations

g = nx.erdos_renyi_graph(n=18, p=0.8, seed=17)
a = nx.nx_agraph.to_agraph(g)
a.layout(prog='circo')

clique, ind_set = ramsey_R2(g)
print(clique, ind_set)

for v in ind_set:
    a.get_node(v).attr['style'] = 'filled'
    a.get_node(v).attr['fillcolor'] = 'grey72'
for u, v in combinations(clique, 2):
    a.get_edge(u, v).attr['color'] = 'deepskyblue'
    a.get_edge(u, v).attr['penwidth'] = 2

a.draw('ramsey_example_colored.png')

{0, 1, 6, 7, 8, 11, 17} {16, 0, 2, 3}

But a maximum independent set can be found quickly in a bipartite graph. More on this in the next section.