Densest Subgraph Greedy

Problem

Approximate the densest subgraph by repeatedly deleting the minimum-degree node (ties by smallest index).

After each deletion record the density edges/nodes and keep the best seen, returning [best_density, best_size]. n is the number of nodes and edges is a list of [u, v] pairs.

Hint

This greedy is a 1/2 approximation to the densest subgraph problem.

Test cases

case 1

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

expected: [1,4]

case 2

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

expected: [1.5,4]

case 3

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

expected: [0.5,2]

Starter codePython

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

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