Greedy Dominating Set Size

Problem

Build a dominating set greedily: every node must be in the set or adjacent to a node in it.

While some node is uncovered, choose the uncovered node that covers the most uncovered nodes (ties broken by smallest index), add it to the set, and mark its closed neighborhood covered. Return the set size. edges is a list of [u, v] pairs.

Hint

Each step picks the node covering the largest number of still-uncovered nodes.

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: 1

case 3

in: [3,[]]

expected: 3

case 4

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

expected: 1

case 5

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

expected: 2

Starter codePython

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

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