Module expander 

Expander Decomposition for Subpolynomial Dynamic Min-Cut

Implements deterministic expander decomposition following:

• Chuzhoy et al. “Deterministic Algorithms for Decremental Approximate Shortest Paths”
• Saranurak-Wang “Expander Decomposition and Pruning”

Key property: Decomposes graph into φ-expanders where φ = 1/(log^{O(1)} n)

Overview

An expander decomposition partitions a graph into components where each component has high expansion (conductance). This is critical for achieving subpolynomial update time because:

1. Updates within an expander can be handled efficiently
2. The decomposition has O(log n) levels
3. Only O(log n / log log n) levels are affected per update

Algorithm

The decomposition uses a recursive trimming approach:

1. Trimming: Identify and remove low-conductance components
2. Recursive Partition: Split remaining graph and recurse
3. Hierarchical Structure: Build O(log n) level hierarchy
4. Dynamic Updates: Maintain decomposition under edge insertions/deletions

Complexity

• Build: O(m log n) where m = edges, n = vertices
• Conductance computation: O(m)
• Update: O(log n) levels affected, O(m’) work per level

Example

use std::sync::Arc;
use ruvector_mincut::graph::DynamicGraph;
use ruvector_mincut::expander::ExpanderDecomposition;

// Create a graph
let graph = Arc::new(DynamicGraph::new());
graph.insert_edge(1, 2, 1.0).unwrap();
graph.insert_edge(2, 3, 1.0).unwrap();
graph.insert_edge(3, 1, 1.0).unwrap();

// Build expander decomposition with conductance threshold
let phi = 0.1; // Conductance threshold
let mut decomp = ExpanderDecomposition::build(graph.clone(), phi).unwrap();

// Query decomposition
println!("Number of levels: {}", decomp.num_levels());

// Handle dynamic updates
decomp.insert_edge(1, 4).unwrap();
decomp.delete_edge(2, 3).unwrap();

Structs

ExpanderComponent

A component in the expander decomposition

ExpanderDecomposition

Hierarchical expander decomposition

Functions

deterministic_decompose

Deterministic expander decomposition using trimming

estimate_conductance

Spectral gap computation for conductance estimation

Type Aliases

Conductance

Expansion (conductance) threshold