Cheeger Check Lite

Problem

Verify the Cheeger inequality on a small graph: the edge conductance h(G) is at most sqrt(2 * lambda2), where lambda2 is the second smallest Laplacian eigenvalue.

Compute h(G) by brute-forcing every non-trivial subset and its conductance. Return True when h(G) is at most the bound plus tol. edges is a list of [u, v] pairs.

Hint

Cheeger relates the best cut to the spectral gap, both ways up to square roots.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3],[3,0]],2,1e-9]

expected: true

case 2

in: [3,[[0,1],[1,2],[2,0]],3,1e-9]

expected: true

case 3

in: [4,[[0,1],[1,2],[2,3]],0.01,1e-9]

expected: false

case 4

in: [4,[[0,1],[1,2],[2,3]],0.5,1e-9]

expected: true

Starter codePython

import math
def cheeger_check(n, edges, spectral_gap, tol):
    # Your code here
    pass

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