Multilevel Partition Lite

Problem

Coarsen an undirected graph repeatedly with greedy matching until at most k nodes remain.

Each round matches nodes pairwise, contracts matched pairs into supernodes, and deduplicates the contracted edges. Return [levels, final_node_count]; stop early if a round cannot match anything.

Hint

Multilevel partitioning alternates coarsening, initial partitioning, and refinement.

Test cases

case 1

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

expected: [2,2]

case 2

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

expected: [2,1]

case 3

in: [3,[],2]

expected: [1,3]

Starter codePython

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

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