Skip to content

Latest commit

 

History

History
318 lines (251 loc) · 9.15 KB

localkcut-paper-implementation.md

File metadata and controls

318 lines (251 loc) · 9.15 KB

Local K-Cut Paper Implementation

Overview

This document describes the paper-compliant implementation of the Local K-Cut algorithm from the December 2024 paper "Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size" (arxiv:2512.13105).

Location

  • Implementation: /home/user/ruvector/crates/ruvector-mincut/src/localkcut/paper_impl.rs
  • Tests: Embedded in paper_impl.rs (16 comprehensive tests)
  • Integration Tests: /home/user/ruvector/crates/ruvector-mincut/tests/localkcut_paper_integration.rs

API Specification

Core Types

LocalKCutQuery

pub struct LocalKCutQuery {
    /// Seed vertices defining the search region
    pub seed_vertices: Vec<VertexId>,

    /// Maximum acceptable cut value
    pub budget_k: u64,

    /// Maximum search radius (BFS depth)
    pub radius: usize,
}

LocalKCutResult

pub enum LocalKCutResult {
    /// Found a cut with value ≤ budget_k
    Found {
        witness: WitnessHandle,
        cut_value: u64,
    },

    /// No cut ≤ budget_k found in the local region
    NoneInLocality,
}

LocalKCutOracle (Trait)

pub trait LocalKCutOracle: Send + Sync {
    fn search(&self, graph: &DynamicGraph, query: LocalKCutQuery) -> LocalKCutResult;
}

Implementation

DeterministicLocalKCut

pub struct DeterministicLocalKCut {
    max_radius: usize,
    family_generator: DeterministicFamilyGenerator,
}

impl DeterministicLocalKCut {
    pub fn new(max_radius: usize) -> Self;

    pub fn with_family_generator(
        max_radius: usize,
        family_generator: DeterministicFamilyGenerator,
    ) -> Self;
}

impl LocalKCutOracle for DeterministicLocalKCut {
    fn search(&self, graph: &DynamicGraph, query: LocalKCutQuery) -> LocalKCutResult;
}

Algorithm Details

Deterministic Properties

  1. No Randomness: The algorithm is completely deterministic

    • BFS exploration order determined by sorted vertex IDs
    • Seed selection based on deterministic ordering
    • Same input always produces same output

  2. Bounded Range: Searches for cuts with value ≤ budget_k

    • Early termination when budget exceeded
    • Returns smallest cut found or NoneInLocality

  3. Local Exploration: BFS-based approach

    • Starts from seed vertices
    • Expands outward layer by layer
    • Tracks boundary size at each layer
    • Returns witness when cut found

Time Complexity

  • Per Query: O(radius × (|V| + |E|)) worst case
  • Typical: Much faster due to early termination
  • Deterministic: No probabilistic guarantees needed

Usage Examples

Basic Usage

use ruvector_mincut::{
    DynamicGraph, LocalKCutQuery, PaperLocalKCutResult,
    LocalKCutOracle, DeterministicLocalKCut,
};
use std::sync::Arc;

// Create 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, 4, 1.0).unwrap();

// Create oracle
let oracle = DeterministicLocalKCut::new(5);

// Create query
let query = LocalKCutQuery {
    seed_vertices: vec![1],
    budget_k: 2,
    radius: 3,
};

// Execute search
match oracle.search(&graph, query) {
    PaperLocalKCutResult::Found { cut_value, witness } => {
        println!("Found cut with value: {}", cut_value);
        println!("Witness cardinality: {}", witness.cardinality());
    }
    PaperLocalKCutResult::NoneInLocality => {
        println!("No cut found in locality");
    }
}

With Custom Family Generator

let generator = DeterministicFamilyGenerator::new(5);
let oracle = DeterministicLocalKCut::with_family_generator(10, generator);

let query = LocalKCutQuery {
    seed_vertices: vec![1, 2, 3],
    budget_k: 5,
    radius: 8,
};

let result = oracle.search(&graph, query);

Accessing Witness Details

if let PaperLocalKCutResult::Found { witness, cut_value } = result {
    // Check witness properties
    assert_eq!(witness.boundary_size(), cut_value);
    assert!(witness.contains(witness.seed()));

    // Materialize full partition (expensive)
    let (u, v_minus_u) = witness.materialize_partition();
    println!("Cut separates {} from {} vertices", u.len(), v_minus_u.len());
}

Test Coverage

Unit Tests (16 tests)

  1. API Tests

    • test_local_kcut_query_creation - Query structure creation
    • test_deterministic_family_generator - Family generator determinism
    • test_deterministic_local_kcut_creation - Oracle instantiation

  2. Algorithm Tests

    • test_simple_path_cut - Basic path graph
    • test_triangle_no_cut - Graph with no small cuts
    • test_dumbbell_bridge_cut - Finding bridge in dumbbell graph
    • test_determinism - Verify deterministic behavior

  3. Edge Case Tests

    • test_empty_seeds - Empty seed list
    • test_invalid_seed - Non-existent vertex
    • test_zero_radius - No expansion
    • test_large_radius - Radius capping

  4. Correctness Tests

    • test_boundary_calculation - Boundary size computation
    • test_witness_creation - Witness handle creation
    • test_multiple_seeds - Multiple starting points
    • test_budget_enforcement - Budget constraints
    • test_witness_properties - Witness invariants

Integration Tests (10 tests)

See /home/user/ruvector/crates/ruvector-mincut/tests/localkcut_paper_integration.rs

Module Structure

ruvector-mincut/
├── src/
│   └── localkcut/
│       ├── mod.rs (updated with exports)
│       └── paper_impl.rs (new implementation)
├── tests/
│   └── localkcut_paper_integration.rs (new)
└── docs/
    └── localkcut-paper-implementation.md (this file)

Exports

The paper implementation is exported at the crate root:

pub use localkcut::{
    // Paper API types
    LocalKCutQuery,
    LocalKCutResult as PaperLocalKCutResult,  // Aliased to avoid conflict
    LocalKCutOracle,

    // Implementation
    DeterministicLocalKCut,
    DeterministicFamilyGenerator,

    // Original implementation (still available)
    LocalKCut,
    LocalCutResult,
    EdgeColor,
    ColorMask,
    ForestPacking,
};

Key Features

1. Strict API Compliance

  • Matches paper specification exactly
  • Clear enum variants for results
  • Witness-based certification

2. Deterministic Algorithm

  • No randomness whatsoever
  • Sorted vertex traversal
  • Reproducible results

3. Efficient Implementation

  • Early termination on budget violation
  • BFS layer-by-layer expansion
  • Minimal memory allocation

4. Comprehensive Testing

  • 16 unit tests covering all functionality
  • 10 integration tests
  • Edge case coverage
  • Determinism verification

Differences from Original Implementation

Feature Original LocalKCut Paper Implementation
API find_cut(v) returns Option<LocalCutResult> search(graph, query) returns LocalKCutResult enum
Input Single vertex + k parameter Query struct with seeds, budget, radius
Output Result struct with various fields Enum: Found or NoneInLocality
Witness Optional in result Always included when found
Determinism Uses edge coloring BFS with sorted traversal
Complexity 4^d enumerations Single deterministic BFS

Performance Characteristics

  • Best Case: O(radius) when cut found immediately
  • Average Case: O(radius × avg_degree × |found_vertices|)
  • Worst Case: O(radius × (|V| + |E|))
  • Memory: O(|V|) for visited set

Future Enhancements

  1. Parallel Search: Multiple seeds in parallel
  2. Incremental Updates: Cache results across queries
  3. Adaptive Radius: Auto-tune radius based on graph density
  4. Witness Compression: Reduce witness storage
  5. Batch Queries: Process multiple queries efficiently

References

  • Paper: "Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size"
  • ArXiv: https://arxiv.org/abs/2512.13105
  • Implementation: /home/user/ruvector/crates/ruvector-mincut/src/localkcut/paper_impl.rs

Verification

All 16 unit tests pass:

cargo test -p ruvector-mincut --lib localkcut::paper_impl::tests

Expected output:

running 16 tests
test localkcut::paper_impl::tests::test_boundary_calculation ... ok
test localkcut::paper_impl::tests::test_budget_enforcement ... ok
test localkcut::paper_impl::tests::test_determinism ... ok
test localkcut::paper_impl::tests::test_deterministic_family_generator ... ok
test localkcut::paper_impl::tests::test_deterministic_local_kcut_creation ... ok
test localkcut::paper_impl::tests::test_dumbbell_bridge_cut ... ok
test localkcut::paper_impl::tests::test_empty_seeds ... ok
test localkcut::paper_impl::tests::test_invalid_seed ... ok
test localkcut::paper_impl::tests::test_large_radius ... ok
test localkcut::paper_impl::tests::test_local_kcut_query_creation ... ok
test localkcut::paper_impl::tests::test_multiple_seeds ... ok
test localkcut::paper_impl::tests::test_simple_path_cut ... ok
test localkcut::paper_impl::tests::test_triangle_no_cut ... ok
test localkcut::paper_impl::tests::test_witness_creation ... ok
test localkcut::paper_impl::tests::test_witness_properties ... ok
test localkcut::paper_impl::tests::test_zero_radius ... ok

test result: ok. 16 passed; 0 failed