Max_set | Python Fiddle

import random
import time
# Generate a random graph where eacg possible edge is in the graph with
# probability 1/2.
def generate_graph(n):
    arr = {}
    for i in range(0, n):
        arr[i] = []
    for vertex in range(0, n):
        for neighbor in range(vertex + 1, n):
            flip_coin = random.randint(0, 1)
            if flip_coin == 0: #Put an edge with 0.5 probability
                arr[vertex].append(neighbor)
                arr[neighbor].append(vertex)
    return arr

def printGraph(graph):
    for vertex in graph.iterkeys():
        print str(vertex) + ": ",
        for neighbor in graph[vertex]:
            print str(neighbor) + " ",
        print

def remove_vertex(graph, vertex):
    return graph.pop(vertex, -1)

def compute_subgraph(graph, vertices):
    copy = dict(graph)
    for vertex in vertices:
        copy.pop(vertex, -1)
    # print("Graph:")
    # printGraph(graph)
    # print("End Graph")
    # print("Subgraph:")
    # printGraph(copy)
    # print("End Subgraph")
    return copy

def nonempty_vertex(graph):
    # Return first valid key
    for vertex in graph.iterkeys():
        return vertex

def max_indep_set(graph):
    if len(graph) == 0:
        return []
    vertex = nonempty_vertex(graph)
    # Let vertex be an arbitrary vertex
    if vertex is None:
        return []
    neighbors = graph[vertex]
    # print("vertex: " + str(vertex) + " neighbors: " + str(neighbors) + " neighbors and vertex: " + str(neighbors + [vertex]))
    s1 = [vertex] + max_indep_set(compute_subgraph(graph, neighbors + [vertex]))
    # print("s1: " + str(s1))
    if len(neighbors) == 0 or len(neighbors) == 1:
        return s1
    # print("vertex: " + str(vertex))
    # printGraph(graph)
    s2 = max_indep_set(compute_subgraph(graph, [vertex]))
    # print("s2: " + str(s2))
    if s1 is None:
        s1 = []
    if s2 is None:
        s2 = []
    if len(s2) > len(s1):
        return s2
    else:
        return s1

sumI = 0
for i in range(0, 10):
    graph = generate_graph(512)
    start = time.time()
    max_set = max_indep_set(graph)
    end = time.time()
    sumI += len(max_set)
print "Runtime: " + str((end - start)) + "Avg Size: " + str(sumI/10.0)

Python Fiddle

Python Cloud IDE