HLPL / VerTeX Modelling Language Documentation

← lessons

Minimum vertex cover

The fewest vertices that touch every edge.

Chapter: XIIb — Graph theory · lesson id gt-vertex-cover · practice lesson

---

A $vertex\ cover$ is a set of vertices such that every edge has at least one endpoint in the set — think of it as placing a guard on a vertex so it watches every incident corridor, and wanting every corridor watched with the fewest guards.

One binary variable y_v per vertex (1 = chosen). One constraint per edge {u, v}: y_u + y_v >= 1, i.e. at least one endpoint is chosen. Minimise the number of chosen vertices.

On our graph the answer is 2: guarding the two hubs, vertices 1 and 5, covers all six edges. Every edge touches 1 or 5 — which is exactly what it means for {1, 5} to be one side of the bipartition.

Predict before running

Edges {1,2},{1,3},{1,4},{2,5},{4,5},{5,6}. What is the fewest vertices that together touch every edge?

• 2 — the two hubs {1, 5}
• 3 — one hub plus a leaf
• 4 — the independent-set side {2, 3, 4, 6}

Starter code

model vc
set V = {1, 2, 3, 4, 5, 6}
bin y, forall v in V
# TODO: one "y_u + y_v >= 1" constraint per edge
#   edges: 12, 13, 14, 25, 45, 56
min sum_{v in V}{y_{v}}
end

import elytica
def main():
  elytica.init_model("vc")
  elytica.run_model("vc")
  for i in [1,2,3,4,5,6]:
    print("y"+str(i), "=", elytica.get_variable_value("vc", "y"+str(i)))
  print("obj =", elytica.get_best_primal_bound("vc"))
  return 0

Hint

Six edges → six "y_u + y_v >= 1" constraints. Vertices 1 and 5 alone cover everything.

What counts as correct

• no-error — Model solves
• numeric-match — Minimum vertex cover uses 2 vertices
• numeric-match — Hub 1 is in the cover
• numeric-match — Hub 5 is in the cover
• code-contains — Reads the objective from the solver (no hardcoding)
• code-contains — Reads variable values from the solver (no hardcoding)

Solution

model vc
set V = {1, 2, 3, 4, 5, 6}
bin y, forall v in V
constr y_{1} + y_{2} >= 1
constr y_{1} + y_{3} >= 1
constr y_{1} + y_{4} >= 1
constr y_{2} + y_{5} >= 1
constr y_{4} + y_{5} >= 1
constr y_{5} + y_{6} >= 1
min sum_{v in V}{y_{v}}
end

import elytica
def main():
  elytica.init_model("vc")
  elytica.run_model("vc")
  for i in [1,2,3,4,5,6]:
    print("y"+str(i), "=", elytica.get_variable_value("vc", "y"+str(i)))
  print("obj =", elytica.get_best_primal_bound("vc"))
  return 0

Mastery variant

A different graph: a triangle {1,2,3} with a tail out to vertex 4. Cover every edge.

model vc_v
# triangle 1-2-3 plus a pendant edge 3-4
set V = {1, 2, 3, 4}
bin y, forall v in V
# TODO: cover edges 12, 13, 23, 34
min sum_{v in V}{y_{v}}
end

import elytica
def main():
  elytica.init_model("vc_v")
  elytica.run_model("vc_v")
  for i in [1,2,3,4]:
    print("y"+str(i), "=", elytica.get_variable_value("vc_v", "y"+str(i)))
  print("obj =", elytica.get_best_primal_bound("vc_v"))
  return 0

Read this through MCP: read with path: "lessons/gt-vertex-cover", or resource hlpl://lessons/gt-vertex-cover.