Independent Set Local Search

Problem

Grow a given independent set by first adding every node not adjacent to it, then repeatedly try (1,2)-swaps: replace one set node adjacent to exactly one outside node with that outside node when it increases the size after greedy completion.

Return the final set sorted. edges is a list of [u, v] pairs and initial lists the starting independent set.

Hint

Local search escapes bad starting sets by exchanging one node for several.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3]],[0]]

expected: [0,2]

case 2

in: [4,[[0,1],[0,2],[0,3]],[0]]

expected: [1,2,3]

case 3

in: [3,[],[1]]

expected: [0,1,2]

Starter codePython

def independent_set_local_search(n, edges, initial):
    # Your code here
    pass

3 test cases · run your code against them in the editor