Spectral Partition Cut Weight

Problem

Compute the number of edges crossing the spectral bipartition of a connected graph.

After seeding random with 12345, run 3000 deflated power iterations on M = (d_max + 1) * I - L with the constant direction removed, so the vector converges to the Fiedler eigenvector; flip it so its largest-magnitude entry is positive, then split nodes by sign (non-negative versus negative). edges is a list of [u, v] pairs. Return the count of edges between the two sides.

Hint

Subtracting the mean each round keeps the power iteration orthogonal to the constant eigenvector.

Test cases

case 1

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

expected: 1

case 2

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

expected: 1

case 3

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

expected: 2

case 4

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

expected: 1

Starter codePython

import random
def spectral_cut_weight(n, edges):
    # Your code here
    pass

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