Solving Vertex Cover Problems with Grove

A Go-first walkthrough of vertex cover modeling, visualization (D3 and Graphviz), and LP-based solving with Grove.

The vertex cover problem

Consider an undirected graph \(G\) with vertices \(V = \{1, \ldots, n\}\) and undirected edges \(E\). Since the graph is undirected, we consider edges \((i,j)\) and \((j,i)\) to be the same.

Vertex cover A vertex cover of the graph is a subset \(C \subseteq V\) such that every edge \(e \in E\) has at least one of its endpoints in the set \(C\).

Note that the entire vertex set \(V\) is trivially a vertex cover. The vertex cover problem asks for the smallest size (cardinality) vertex cover for a given undirected graph \(G\).

Practical application Draw a map: the dots are sites (cities, substations, offices) and the lines are the connections you must service (highways, power lines, leased fiber). You can only post crews, trucks, or monitors at the dots, not in the middle of a line. A vertex cover is the fewest dots to choose so that every line touches at least one of them—the usual “cover every link from an endpoint, with as few bases as possible” story.

Minimum vertex cover is NP-hard in general. A standard optimization view is to write the problem as an integer linear program, then either solve it exactly with a MIP-capable engine or relax integrality, solve the LP, and round.

What follows sets up the ILP, implements the LP relaxation in Grove, and applies the usual \(\tfrac{1}{2}\)-threshold rounding—with D3 for the in-page example and a Graphviz-backed Go helper for scriptable plots.

Example

Consider the example below: a graph on five nodes with the cover shaded orange. The set \(\{1,4,5\}\) is a vertex cover, and \(\{4,5\}\) is a smaller (minimum) cover.

Edge set \(E\):

edge_list = [(1,4), (1,5), (2,5), (2,4), (3,4), (4,5)]

Valid vertex cover: {1, 4, 5}.

Minimum vertex cover: {4, 5}.

Plotting a Graph + Cover in Go

Instead of Python’s networkx + matplotlib, the Go helper renders with Graphviz and highlights selected vertices in orange. plot_graph_with_vc.go is the entry point for that path.

Source on GitLab (edits to the snippet show up here automatically): gitlab.com/-/snippets/5984946

Integer linear programming formulation for vertex cover

Here is a standard integer linear programming formulation. Let \(G\) be a graph with vertices \(V = \{1, \ldots, n\}\) and undirected edges \(E\). The edges \((i,j)\) and \((j,i)\) are taken to be the same.

If you have used a modeling library for linear programming before (for example PuLP in Python), the pieces below will feel familiar; here we implement the same model in Go with Grove.

Decision variables

We have \(n\) decision variables \(w_1, \ldots, w_n\). In the true ILP they are binary: each \(w_i\) takes values in \(\{0,1\}\). The meaning is: \(w_i = 1\) if vertex \(i\) is in the cover, and \(w_i = 0\) if it is not.

In PuLP you might declare a binary variable like this:

wi = LpVariable('w_i', cat='Binary')

In Grove, the corresponding modeling step is to create a variable per vertex; in the code below we use a continuous relaxation \(w_i \in [0,1]\) because Grove’s current built-in solver works with linear programs (the true binary ILP can be added later with a MIP-capable backend).

Objective function

With the decision variables as above, the objective is to minimize how many vertices we select:

\min \;\; w_1 + \cdots + w_n

Minimizing this sum is the same as minimizing the size of the cover.

Constraints

The constraints are: (a) each \(w_i\) is binary in the ILP formulation, and (b) for every edge \((i,j) \in E\), at least one of \(i\) and \(j\) must lie in the cover—equivalently, at least one of \(w_i, w_j\) must be \(1\). One standard linear encoding is:

w_i + w_j \ge 1 \qquad \text{for all edges } (i,j) \in E

Putting it all together

The overall ILP is:

\begin{aligned} \min\quad & \sum_{j=1}^{n} w_j \\ \text{s.t.}\quad & w_i + w_j \ge 1 \qquad \text{for all edges } (i,j) \in E \\ & w_i \in \{0,1\} \qquad \text{for all } i = 1, \ldots, n \end{aligned}

In Go, using Grove today, the built-in solver optimizes the LP relaxation with \(w_i \in [0,1]\), then we round to a cover (see the next section).

Solving with Grove (Go)

vertex_cover_with_grove.go builds the LP relaxation in Grove, then applies the \(w_i \ge \tfrac{1}{2}\) rounding rule.

Source on GitLab: gitlab.com/-/snippets/5984950

Why the \(\tfrac{1}{2}\) threshold works

For each edge \((i,j)\), the LP enforces \(w_i + w_j \ge 1\). Thus \(\max(w_i, w_j) \ge \tfrac{1}{2}\), so the rounded set

C = \Bigl\{\, i \in V \;\Big|\; w_i \ge \tfrac{1}{2} \Bigr\}

is a valid vertex cover. It is the usual 2-approximation obtained from the standard LP relaxation and half-integral rounding (for this vertex-cover LP, extreme points are half-integral).

Install + run locally

The runnable Go is in the two GitLab snippets above; the prose here explains the model without duplicating the full files.

To use them locally, create a new empty directory, cd into it, and run go mod init example.com/vc (or another module path you are allowed to use—that only writes go.mod and labels your module for imports). Then save the snippet source into .go files. If the two snippets are both package main with their own func main, put them in separate directories (each with its own go mod init) or combine the code into one main yourself. Add Grove, then run:

go get github.com/jakenherman/grove@v0.1.0
go run . (or go run a specific .go file)

Graphviz (for the plotting helper only): brew install graphviz (macOS).

Closing note

This approach gives a clean Go workflow: model in Grove, solve the relaxation quickly, and wire plots through Graphviz (or D3 in the page). If you need provably exact minimum covers, use a MIP solver with branch-and-bound. For large graphs where speed matters, LP relaxation plus rounding remains a strong practical baseline.