When one dimension is small

NP-hard does not mean uniformly hard. Real problems often have a small dimension you can exploit.

1. 01
   Fixed-parameter vertex cover — branch on each uncovered edge, recurse with k − 1. Worst case 2ᵏ branches, polynomial in n. For a graph with millions of nodes and a target cover of size 30, the work is feasible.

   fn vertex_cover_fpt(edges: &[(usize, usize)], k: i32) -> Option<Vec<(usize, usize)>> {
       if k < 0 { return None; }
       let uncovered = edges.iter().copied().next();
       let Some((u, v)) = uncovered else { return Some(vec![]); };
       let without_u: Vec<_> = edges.iter().filter(|e| e.0 != u && e.1 != u).copied().collect();
       if let Some(mut sol) = vertex_cover_fpt(&without_u, k - 1) {
           sol.push((u, u));
           return Some(sol);
       }
       let without_v: Vec<_> = edges.iter().filter(|e| e.0 != v && e.1 != v).copied().collect();
       if let Some(mut sol) = vertex_cover_fpt(&without_v, k - 1) {
           sol.push((v, v));
           return Some(sol);
       }
       None
   }

2. 02
   let Some((u, v)) = uncovered else { return Some(vec![]); }; is the let-else pattern (Rust 1.65+). Shape: let PATTERN = EXPRESSION else { DIVERGING_BLOCK };. If the pattern matches the right-hand side, the bindings come into scope normally. If it does not match, the else block runs — and that block must diverge: return, break, continue, panic!, or a function returning ! (the never-type). The point is that the bindings stay in scope for the rest of the enclosing function, no nesting required. Compare with if let Some(x) = … { /* large body using x */ } else { return; } — the let-else version keeps the body at the same indentation level and the early-exit terse. On page 35 the algorithm walks edges recursively; uncovered is the first edge that still needs covering, Option<(usize, usize)>. Either there is one (the function continues with u and v in scope), or there isn't, in which case an empty cover is already a valid answer and the else branch returns it immediately.

   // let-else — bind on success, diverge on failure.
   //
   //   let PATTERN = EXPRESSION else {
   //       /* diverging block: return, break, continue, panic, etc. */
   //   };
   //   /* PATTERN bindings are in scope from here for the rest of the fn */
   
   
   // Page 35's specific line:
   let uncovered: Option<(usize, usize)> = edges.iter().copied().next();
   
   let Some((u, v)) = uncovered else {
       return Some(vec![]);                  // no edges left → empty cover wins
   };
   // u and v are now in scope for the rest of the function.
   
   
   // Same effect with if-let (page 28) — more nesting:
   if let Some((u, v)) = edges.iter().copied().next() {
       // … large body using u and v …
   } else {
       return Some(vec![]);
   }
   
   
   // Same effect with match — even more typing:
   let (u, v) = match edges.iter().copied().next() {
       Some(pair) => pair,
       None       => return Some(vec![]),
   };
   
   
   // The else block is REQUIRED to diverge.  All of these compile:
   let Some(x) = maybe else { return; };
   let Some(x) = maybe else { break; };
   let Some(x) = maybe else { continue; };
   let Some(x) = maybe else { panic!("bug"); };
   let Some(x) = maybe else { std::process::exit(1); };
   
   // Rejected — else must NOT fall through:
   let Some(x) = maybe else { println!("oops"); };   // error: expected divergence
   
   
   // When let-else shines vs if-let:
   //
   //   if-let     equally weighted branches; both have real work to do.
   //
   //   let-else   one happy path, one early-exit.
   //              You want the happy path at the top indentation level.
   //
   // Most "guard clause" early-returns are cleaner as let-else.