HLPL / VerTeX Modelling Language Documentation

← lessons

Maximum independent set

The most vertices with no edge between any two.

Chapter: XIIb — Graph theory · lesson id gt-independent-set · practice lesson

---

An $independent\ set$ is the opposite instinct: pick as $many$ vertices as you can such that no edge joins two of them — a set of mutually non-adjacent vertices.

Same variables, flipped constraint. Binary z_v per vertex; for each edge {u, v} at most one endpoint may be chosen, so z_u + z_v <= 1. Maximise the number chosen.

On our graph the answer is 4: {2, 3, 4, 6} has no edge inside it. Look at what happened — that is exactly the four vertices the minimum cover {1, 5} left out. Cover and independent set are complements.

Predict before running

Same six-vertex graph. What is the largest set of vertices with no edge between any two of them?

• 4 — the vertices {2, 3, 4, 6}
• 2 — the two hubs {1, 5}
• 3 — a path's worth of vertices

Starter code

model is
set V = {1, 2, 3, 4, 5, 6}
bin z, forall v in V
# TODO: one "z_u + z_v <= 1" constraint per edge
#   edges: 12, 13, 14, 25, 45, 56
max sum_{v in V}{z_{v}}
end

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

Hint

Flip the cover: for each edge, z_u + z_v <= 1. The four non-hub vertices {2,3,4,6} are mutually non-adjacent.

What counts as correct

• no-error — Model solves
• numeric-match — Maximum independent set has 4 vertices
• numeric-match — Hub 1 is excluded
• numeric-match — Hub 5 is excluded
• code-contains — Reads the objective from the solver (no hardcoding)
• code-contains — Reads variable values from the solver (no hardcoding)

Solution

model is
set V = {1, 2, 3, 4, 5, 6}
bin z, forall v in V
constr z_{1} + z_{2} <= 1
constr z_{1} + z_{3} <= 1
constr z_{1} + z_{4} <= 1
constr z_{2} + z_{5} <= 1
constr z_{4} + z_{5} <= 1
constr z_{5} + z_{6} <= 1
max sum_{v in V}{z_{v}}
end

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

Mastery variant

The same triangle-with-a-tail graph. How many mutually non-adjacent vertices this time?

model is_v
set V = {1, 2, 3, 4}
bin z, forall v in V
# TODO: z_u + z_v <= 1 for edges 12, 13, 23, 34
max sum_{v in V}{z_{v}}
end

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

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