813 Intermediate

813-minimum-vertex-cover — Minimum Vertex Cover (Trees)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "813-minimum-vertex-cover — Minimum Vertex Cover (Trees)" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. A vertex cover is a set of vertices such that every edge has at least one endpoint in the set. Key difference from OCaml: 1. **Tree DP structure**: Both languages implement the same O(n) tree DP; the recursion pattern is nearly identical.

Tutorial

The Problem

A vertex cover is a set of vertices such that every edge has at least one endpoint in the set. The minimum vertex cover finds the smallest such set. For general graphs this is NP-hard (equivalent to maximum independent set), but for trees it is solvable in O(n) by DP on the tree structure. Applications: network security (placing sensors to monitor all links), database index optimization, and approximation algorithms for general graphs.

🎯 Learning Outcomes

• Implement tree DP with two states per vertex: dp[v][0] (v not in cover) and dp[v][1] (v in cover)

• Apply the recurrence: if v not in cover, all children must be covered

• If v in cover, children may or may not be covered (take minimum)

• Run DFS from the root, computing dp values bottom-up

• Understand König's theorem: in bipartite graphs, max matching = min vertex cover

Code Example

#![allow(clippy::all)]
//! # Minimum Vertex Cover (Trees)
pub fn min_vertex_cover_tree(n: usize, edges: &[(usize, usize)]) -> usize {
    if n == 0 {
        return 0;
    }
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut dp = vec![[0, 0]; n];
    let mut visited = vec![false; n];
    fn dfs(v: usize, adj: &[Vec<usize>], dp: &mut [[usize; 2]], vis: &mut [bool]) {
        vis[v] = true;
        dp[v][0] = 0;
        dp[v][1] = 1;
        for &u in &adj[v] {
            if !vis[u] {
                dfs(u, adj, dp, vis);
                dp[v][0] += dp[u][1];
                dp[v][1] += dp[u][0].min(dp[u][1]);
            }
        }
    }
    dfs(0, &adj, &mut dp, &mut visited);
    dp[0][0].min(dp[0][1])
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_vc() {
        assert_eq!(min_vertex_cover_tree(4, &[(0, 1), (1, 2), (1, 3)]), 1);
    }
}

(* Minimum Vertex Cover — 2-approximation O(V+E) *)

let vertex_cover_2approx n edges =
  let covered = Array.make n false in
  let cover   = ref [] in
  List.iter (fun (u, v) ->
    if not covered.(u) && not covered.(v) then begin
      covered.(u) <- true;
      covered.(v) <- true;
      cover       := u :: v :: !cover
    end
  ) edges;
  List.sort_uniq compare !cover

(* Exact MVC via backtracking — exponential, for small graphs *)
let vertex_cover_exact n edges =
  let best = ref n in
  let mask = ref 0 in

  let rec solve i current_mask current_size =
    if current_size >= !best then ()
    else if i = n then begin
      (* Verify it's a valid cover *)
      let valid = List.for_all (fun (u, v) ->
        current_mask land (1 lsl u) <> 0 ||
        current_mask land (1 lsl v) <> 0
      ) edges in
      if valid && current_size < !best then begin
        best := current_size;
        mask := current_mask
      end
    end else begin
      solve (i+1) current_mask current_size;                        (* skip i *)
      solve (i+1) (current_mask lor (1 lsl i)) (current_size + 1)  (* take i *)
    end
  in
  solve 0 0 0;
  List.init n (fun i -> (i, !mask land (1 lsl i) <> 0))
  |> List.filter_map (fun (i, b) -> if b then Some i else None)

let () =
  let n     = 7 in
  let edges = [(0,1);(0,2);(1,3);(2,3);(3,4);(4,5);(4,6)] in
  let cover2 = vertex_cover_2approx n edges in
  Printf.printf "2-approx cover (%d vertices): [%s]\n"
    (List.length cover2)
    (String.concat "," (List.map string_of_int cover2));
  let cover_exact = vertex_cover_exact n edges in
  Printf.printf "Exact cover (%d vertices): [%s]\n"
    (List.length cover_exact)
    (String.concat "," (List.map string_of_int cover_exact))

Key Differences

Tree DP structure: Both languages implement the same O(n) tree DP; the recursion pattern is nearly identical.

Parent tracking: Both need to avoid revisiting the parent edge; Rust uses vis array, OCaml passes parent explicitly.

General graphs: For general graphs, minimum vertex cover is NP-hard; the 2-approximation (take both endpoints of each maximal matching edge) works in both languages.

König's theorem: In bipartite graphs, the minimum vertex cover equals maximum matching size — a deep connection enabling polynomial solutions for bipartite instances.

OCaml Approach

OCaml implements tree DP with Array.make n [|0; 0|] and recursive DFS. let rec dfs v parent = ... List.iter (fun u -> if u <> parent then (dfs u v; ...)) adj.(v). The DP update is: dp.(v).(0) <- dp.(v).(0) + dp.(u).(1) and dp.(v).(1) <- dp.(v).(1) + min dp.(u).(0) dp.(u).(1). OCaml's pattern matching makes the two cases readable.

Full Source

#![allow(clippy::all)]
//! # Minimum Vertex Cover (Trees)
pub fn min_vertex_cover_tree(n: usize, edges: &[(usize, usize)]) -> usize {
    if n == 0 {
        return 0;
    }
    let mut adj = vec![vec![]; n];
    for &(u, v) in edges {
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut dp = vec![[0, 0]; n];
    let mut visited = vec![false; n];
    fn dfs(v: usize, adj: &[Vec<usize>], dp: &mut [[usize; 2]], vis: &mut [bool]) {
        vis[v] = true;
        dp[v][0] = 0;
        dp[v][1] = 1;
        for &u in &adj[v] {
            if !vis[u] {
                dfs(u, adj, dp, vis);
                dp[v][0] += dp[u][1];
                dp[v][1] += dp[u][0].min(dp[u][1]);
            }
        }
    }
    dfs(0, &adj, &mut dp, &mut visited);
    dp[0][0].min(dp[0][1])
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_vc() {
        assert_eq!(min_vertex_cover_tree(4, &[(0, 1), (1, 2), (1, 3)]), 1);
    }
}

(* Minimum Vertex Cover — 2-approximation O(V+E) *)

let vertex_cover_2approx n edges =
  let covered = Array.make n false in
  let cover   = ref [] in
  List.iter (fun (u, v) ->
    if not covered.(u) && not covered.(v) then begin
      covered.(u) <- true;
      covered.(v) <- true;
      cover       := u :: v :: !cover
    end
  ) edges;
  List.sort_uniq compare !cover

(* Exact MVC via backtracking — exponential, for small graphs *)
let vertex_cover_exact n edges =
  let best = ref n in
  let mask = ref 0 in

  let rec solve i current_mask current_size =
    if current_size >= !best then ()
    else if i = n then begin
      (* Verify it's a valid cover *)
      let valid = List.for_all (fun (u, v) ->
        current_mask land (1 lsl u) <> 0 ||
        current_mask land (1 lsl v) <> 0
      ) edges in
      if valid && current_size < !best then begin
        best := current_size;
        mask := current_mask
      end
    end else begin
      solve (i+1) current_mask current_size;                        (* skip i *)
      solve (i+1) (current_mask lor (1 lsl i)) (current_size + 1)  (* take i *)
    end
  in
  solve 0 0 0;
  List.init n (fun i -> (i, !mask land (1 lsl i) <> 0))
  |> List.filter_map (fun (i, b) -> if b then Some i else None)

let () =
  let n     = 7 in
  let edges = [(0,1);(0,2);(1,3);(2,3);(3,4);(4,5);(4,6)] in
  let cover2 = vertex_cover_2approx n edges in
  Printf.printf "2-approx cover (%d vertices): [%s]\n"
    (List.length cover2)
    (String.concat "," (List.map string_of_int cover2));
  let cover_exact = vertex_cover_exact n edges in
  Printf.printf "Exact cover (%d vertices): [%s]\n"
    (List.length cover_exact)
    (String.concat "," (List.map string_of_int cover_exact))

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_vc() {
        assert_eq!(min_vertex_cover_tree(4, &[(0, 1), (1, 2), (1, 3)]), 1);
    }
}

Deep Comparison

OCaml vs Rust: Minimum Vertex Cover

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement min_vertex_cover_reconstruct(n, edges) -> Vec<usize> that returns the actual vertices in the cover, not just the count.

Implement the 2-approximation for general graphs: find a maximal matching and include both endpoints of each matched edge. Verify the result is a valid cover.

Implement maximum independent set for trees: since MIS = n - MVC, use the tree DP to compute both. Verify MVC + MIS = n.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust