Function min_vertex_cut 

pub fn min_vertex_cut(
    graph: &SqliteGraph,
    source: i64,
    target: i64,
) -> Result<MinVertexCutResult, SqliteGraphError>

Compute minimum vertex cut using vertex splitting transformation.

Returns the smallest set of vertices whose removal disconnects source from sink. Uses vertex splitting to convert vertex cut to edge cut, then applies max-flow.

Arguments

• graph - The graph to analyze
• source - The source node ID
• target - The target node ID

Returns

MinVertexCutResult containing separator, source_side, sink_side, and cut_size.

Algorithm

1. Transform graph using vertex splitting: each vertex x becomes (x_in, x_out)
2. Add edge (x_in, x_out) with capacity 1 for each vertex
3. For each original edge (u, v), add edge (u_out, v_in) with capacity 1
4. Run max-flow on transformed graph
5. Extract separator: vertices where (x_in, x_out) edge is saturated

Complexity

• Time: O(|V| * |E|²) for Edmonds-Karp with ~2V vertices
• Space: O(|V| + |E|) for transformed graph and residual graph

Edge Cases

• Source == Target: Returns empty separator (trivially connected)
• Direct edge source->target: Returns empty separator (no intermediate vertices)
• Disconnected nodes: Returns empty separator

Example

use sqlitegraph::{SqliteGraph, algo::min_vertex_cut};

let graph = SqliteGraph::open_in_memory()?;
// ... build graph ...

let result = min_vertex_cut(&graph, 1, 5)?;
println!("Remove these vertices to disconnect: {:?}", result.separator);
println!("Separator size: {}", result.cut_size);