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. simpleInterleavedVC is simpleFptVertexCover with a kernelization rule applied in every call: a vertex of degree $> k$ must be in every cover of size $\le k$, so it is taken right away; betterInterleavedVC applies all rules of Buss's kernel in every call of betterFptVertexCover. With “stop at the first cover found”, the search ends as soon as some call returns a cover, which settles the decision problem. Click a node of the tree to jump there.
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.
k 5 (or k = 5) anywhere sets the parameter; lines starting with
# are comments. Parallel edges are merged, self-loops are refused.