independence_number.sagews

def neighbors(g,v):
    N = []
    E = g.edges(labels=False)
    for w in g.vertices():
        if (v,w) in E or (w,v) in E:
            N.append(w)
    return N

pete = graphs.PetersenGraph()

neighbors(pete,0)

[1, 4, 5]

def remove_vertex_and_neighbors(g,v):
    S2=g.vertices()
    S2.remove(v)
    for w in neighbors(g,v):
        S2.remove(w)
    return g.subgraph(S2)

def tt_maximum_independent_set(g, IndependentSet):
    V = g.vertices()
    if V == []:
        return IndependentSet
    v = V.pop()
    S1 = V
    S2 = remove_vertex_and_neighbors(g,v)
    g1 = g.subgraph(S1)
    g2 = g.subgraph(S2)
    Max1 = tt_maximum_independent_set(g1, IndependentSet)
    Max2 = tt_maximum_independent_set(g2, IndependentSet+[v])
    if len(Max1) > len(Max2):
        return Max1
    else:
        return Max2

tt_maximum_independent_set(pete,[])

[9, 8, 2, 0]

def tt_independence_number(g):
    return len(tt_maximum_independent_set(g,[]))

tt_independence_number(pete)

4

pete.is_independent_set([0,1])

False

def naive_maximum_independent_set(g):
    largest = 0
    independent = []
    L=subsets(g.vertices())
    for S in L:
        if g.is_independent_set(S):
            if len(S) > largest:
                largest = len(S)
                independent = S
    return independent

naive_maximum_independent_set(pete)

[2, 4, 5, 6]

pete.show()

def naive_independence_number(g):
    return len(naive_maximum_independent_set(g))

naive_independence_number(pete)

4

timeit("naive_independence_number(pete)")

5 loops, best of 3: 93 ms per loop

timeit("tt_independence_number(pete)")

25 loops, best of 3: 15.1 ms per loop

pete.independent_set(value_only = True)

4

timeit("pete.independent_set(value_only = True)")

625 loops, best of 3: 281 µs per loop

dodo = graphs.DodecahedralGraph()

dodo.show()

timeit("tt_independence_number(dodo)")

5 loops, best of 3: 1.19 s per loop

timeit("dodo.independent_set(value_only = True)")

625 loops, best of 3: 614 µs per loop

timeit("naive_independence_number(dodo)")

5 loops, best of 3: 168 s per loop