Maximum Independent Set Greedy

Problem

Build an independent set greedily with the minimum-degree heuristic.

Repeatedly select the remaining node with the smallest current degree (ties broken by smallest index), add it to the set, and delete it together with its neighbors. Return the size of the resulting independent set. edges is a list of [u, v] pairs.

Hint

Choosing low-degree nodes first tends to keep many nodes available.

Test cases

case 1

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

expected: 2

case 2

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

expected: 3

case 3

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

expected: 1

case 4

in: [3,[]]

expected: 3

Starter codePython

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

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