Chapter VII Feedback Node Set

Cycle hunting in Go

Go's goroutines aren't the point here — but its struct-of-slices style and tight loops make graph algorithms read clean.

Adjacency list as a slice-of-slices. Vertices are int indices; the graph is just g[u] = list of successors. No fancy types — Go encourages the boring representation.

type Graph [][]int

func (g Graph) hasCycle() bool {
    n := len(g)
    color := make([]int, n) // 0=white, 1=gray, 2=black
    var dfs func(u int) bool
    dfs = func(u int) bool {
        color[u] = 1
        for _, v := range g[u] {
            if color[v] == 1 { return true }
            if color[v] == 0 && dfs(v) { return true }
        }
        color[u] = 2
        return false
    }
    for u := 0; u < n; u++ {
        if color[u] == 0 && dfs(u) { return true }
    }
    return false
}

Branch-and-bound for FVS — pick a vertex on a known cycle and either include it in the set or recurse on the rest. The branch-on-cycle insight is what makes the FPT algorithms work.

func fvs(g Graph, k int) ([]int, bool) {
    if !g.hasCycle()      { return nil, true }
    if k == 0             { return nil, false }
    v := g.anyOnCycle()
    sub := g.removeVertex(v)
    if got, ok := fvs(sub, k-1); ok {
        return append(got, v), true
    }
    return nil, false
}

03

Find the minimum k by binary search or a simple linear scan. In production graphs with thousands of vertices, you'd kernelize first — collapse vertices of degree 0 or 1, contract chains — but the recursion above is the engine.
```
func minFVS(g Graph) []int {
    for k := 0; k <= len(g); k++ {
        if got, ok := fvs(g, k); ok { return got }
    }
    return nil
}
```
04

Drive it. For a graph with cycles A→B→C→A and A→D→A, the algorithm reports {A} — a single vertex on the intersection of both cycles, breaking them in one cut.
```
func main() {
    g := Graph{{1,3}, {2}, {0}, {0}}
    fmt.Println(minFVS(g)) // [0]
}
```

Grammar — Go

Go is small on purpose: a handful of types, a handful of keywords, and the compiler does the rest. Graph algorithms read as plain procedural code with no ceremony.

package main: every Go file declares its package. main is the executable entry point.
type Graph [][]int: a named type built from a slice-of-slices. Methods can attach to any named type.
func (g Graph) m(): a method on Graph. The receiver g comes before the method name.
make([]int, n): allocate a slice of length n. Slices grow with append.
var f func(int) bool: declare a function-typed variable — useful for recursive closures.
for _, v := range g[u]: iterate over a slice. The blank identifier _ discards the index.
:=: short variable declaration — declare-and-assign in one step.
if cond { return ... }: no parentheses around the condition; braces always required.
{x, y}: a composite literal. For slices: []int{1, 2, 3}; for structs: Point{x: 1, y: 2}.

Cycle detection by three-coloring: white = unvisited, gray = on the current DFS stack, black = finished. A neighbor that's gray means we've walked into our own ancestor — a cycle.

color := make([]int, n) // all 0 (white)
var dfs func(u int) bool
dfs = func(u int) bool {
    color[u] = 1 // gray
    for _, v := range g[u] {
        if color[v] == 1 { return true } // back-edge!
        if color[v] == 0 && dfs(v) { return true }
    }
    color[u] = 2 // black
    return false
}

The Go Playground — run Go in your browser →