Chapter V Vertex Cover

Branching in Haskell

Pure recursion with sets. Haskell's Data.Set keeps the code as close to the math as code gets.

01

Represent the graph as a set of edges, where an edge is a pair of vertices. The whole algorithm will be set operations on this structure — no mutation, no aliasing.
```
import qualified Data.Set as S
type Vertex = Int
type Edge   = (Vertex, Vertex)
type Graph  = S.Set Edge
```

The classic FPT branch: pick any uncovered edge (u,v). Either u is in the cover or v is. Recurse on both, return the smaller result. The recursion depth is bounded by k, not by n.

vcover :: Int -> Graph -> Maybe (S.Set Vertex)
vcover k es
  | S.null es = Just S.empty
  | k == 0    = Nothing
  | otherwise =
      let (u, v) = S.findMin es
          rm x   = S.filter (\(a,b) -> a /= x && b /= x) es
          tryU   = S.insert u <$> vcover (k-1) (rm u)
          tryV   = S.insert v <$> vcover (k-1) (rm v)
      in tryU <|> tryV

03

Wrap it to find the minimum k that works. We start at 0 and increase; the first hit is optimal. (For real workloads use the kernelization tricks too, but they don't change the shape.)
```
import Control.Applicative ((<|>))

minCover :: Graph -> S.Set Vertex
minCover g = head [c | k <- [0..], Just c <- [vcover k g]]
```
04

Try it. The whole solver fits in a third of a screen and reads as the algorithm's English description. That is what Haskell buys you for problems shaped like this.
```
main = do
  let g = S.fromList [(1,2),(2,3),(3,4),(4,1),(2,4)]
  print (minCover g)
-- fromList [2,4]
```

Grammar — Haskell

Haskell is pure: every function is a value mapping inputs to outputs, with no side effects. You describe the problem as algebraic data + transformations, and the compiler picks the evaluation order. Set algorithms read close to their textbook descriptions.

import qualified M as Q: qualified import — the module's names live behind a Q. prefix and won't collide.
type T = ...: a type alias — Edge becomes shorthand for (Vertex, Vertex).
f :: A -> B -> C: a type signature. Arrows associate right; this is A -> (B -> C), so partial application is free.
Maybe a: either Just value or Nothing — explicit absence, no nulls.
<$>: fmap — apply a pure function inside a Functor (f <$> Just 3 = Just (f 3)).
<|>: alternative — try the left; on Nothing, try the right. Backtracking in one operator.
let x = e in body: local binding. let introduces, in is the expression that uses it.
\(a,b) -> ...: a lambda with a destructuring pattern. The backslash is meant to look like a Greek lambda.
[c | k <- [0..]]: a list comprehension — reads as set-builder notation in code.

Vertex cover branching: try the first endpoint; if that finds nothing, try the second. The <|> operator falls through to the right side only when the left returns Nothing.

tryU  = S.insert u <$> vcover (k-1) (rm u)
tryV  = S.insert v <$> vcover (k-1) (rm v)
result = tryU <|> tryV
-- if tryU finds a cover, that wins.
-- otherwise, fall through to tryV.

Try Haskell in your browser →