Module traits 

Core traits for bounded-range minimum cut instances

This module defines the ProperCutInstance trait that all bounded-range minimum cut solvers must implement. The trait provides a unified interface for maintaining minimum proper cuts under dynamic edge updates.

Overview

A proper cut instance maintains the minimum proper cut for a graph under the assumption that the minimum cut value λ ∈ [λ_min, λ_max]. This bounded assumption enables more efficient algorithms than maintaining the exact minimum cut for arbitrary λ values.

Guarantees

• Correctness: If λ ∈ [λ_min, λ_max], the instance returns correct results
• Undefined behavior: If λ < λ_min, behavior is undefined
• Detection: If λ > λ_max, the instance reports AboveRange

Update Model

Updates follow a two-phase protocol:

1. Insert phase: Call apply_inserts() with new edges
2. Delete phase: Call apply_deletes() with removed edges

This ordering ensures graph connectivity is maintained during updates.

Enums

InstanceResult

Result from a bounded-range instance query

Traits

ProperCutInstance

A bounded-range proper cut instance