Vertex Cover · the bounded search tree, step by step

Every edge needs one of its endpoints in the cover, so we can branch on which one, and every branch spends budget: the parameter $k$ drops in each recursive call, and the search stops at $k = 0$. The tree on the right is that search; its size depends only on $k$, not on the size of the graph. simpleFptVertexCover branches on an edge (branching vector $(1,1)$, at most $2^k$ leaves); betterFptVertexCover branches on a vertex $v$ of maximal degree versus all of its neighbours ($(1,d)$ with $d \ge 3$) and solves graphs of maximal degree 2 directly. Click a node of the tree to jump there.

Small screen: the graph and the tree are stacked. Drag a vertex to move it; drag the tree to pan it. The pseudocode scrolls sideways.

Example

Algorithm

Parameter $k$

Detail

— / — Delay 500ms

Graph of the current call

in the cover on this branch (removed) branching on neighbours $w_1,\ldots,w_d$ returned cover drag vertices to rearrange picked in the base case

Search tree graphs in nodes follow

current call $E = \emptyset$: return $\emptyset$ $k = 0$, edges left: truncated degree $\le 2$: solved directly smaller cover chosen

What just happened

Variables of the current call

Size of the search tree

Pseudocode

Input

The algs4 graph format, as written by the graph editor: the number of vertices V, the number of edges E, then E lines v w (vertices are 0…V−1; anything after the two endpoints, such as a weight, is ignored). Optionally V more lines x y give the drawing: any scale, y pointing down, the picture keeps its aspect ratio. Without them the graph is laid out automatically.

A line k 5 (or k = 5) anywhere sets the parameter; lines starting with # are comments. Parallel edges are merged, self-loops are refused.

The tree is computed in full before it is shown, so very large instances are refused: at most 60 vertices and 4000 recursive calls.