Skip to content

Minimum Vertex Cover Example

Download Notebook

The Minimum Vertex Cover problem finds the smallest set of vertices such that every edge has at least one endpoint in the set. It is NP-hard and one of Karp's 21 NP-complete problems.

import getpass
import os

import numpy as np
from dotenv import load_dotenv

from local_solver.scip import SCIP
from luna_usecases.minimum_vertex_cover import (
    MinimumVertexCoverCollection,
    MinimumVertexCoverData,
    MinimumVertexCoverFormulation,
    MinimumVertexCoverInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define a 5-node graph. A vertex cover touches every edge.

adj = np.array(
    [
        [0, 1, 1, 0, 0],
        [1, 0, 1, 1, 0],
        [1, 1, 0, 0, 1],
        [0, 1, 0, 0, 1],
        [0, 0, 1, 1, 0],
    ]
)
node_names = ["A", "B", "C", "D", "E"]
data = MinimumVertexCoverData.from_adjacency_matrix(adjacency_matrix=adj, node_names=node_names)
print(data.to_string())

Minimum Vertex Cover Data:
  Nodes: 5
  Edges: 6

Plot Data

Visualize the graph structure.

data.plot()


<Axes: title={'center': 'Minimum Vertex Cover — 5 nodes, 6 edges'}>
png

Create Formulation

Minimize selected nodes while ensuring every edge has at least one endpoint selected.

formulation = MinimumVertexCoverFormulation()
print(formulation.to_string(data))

Minimum Vertex Cover Formulation:
  Nodes: 5
  Edges: 6

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 4
  x[i] = 1 if node i is in the vertex cover
  Total: 5 binary variables

Objective:
  minimize sum_i x[i]

Constraints:
  1. Edge coverage (6 constraints):
     x[i] + x[j] >= 1  for all edges (i,j)

Create Instance

Combine data and formulation into a solvable instance.

instance = MinimumVertexCoverInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Minimum Vertex Cover Data:
  Nodes: 5
  Edges: 6
Formulation:Minimum Vertex Cover Formulation:
  Nodes: 5
  Edges: 6

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 4
  x[i] = 1 if node i is in the vertex cover
  Total: 5 binary variables

Objective:
  minimize sum_i x[i]

Constraints:
  1. Edge coverage (6 constraints):
     x[i] + x[j] >= 1  for all edges (i,j)

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

2026-05-13 06:40:17 INFO     Running SCIP for model minimum_vertex_cover<minimum_vertex_cover>

                    INFO     Completed SCIP optimization for model minimum_vertex_cover<minimum_vertex_cover> in
                             0.01s

Minimum Vertex Cover Solution:
  Cover size: 3
  Valid: True
  Cover nodes: ['B', 'C', 'E']

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)


<Axes: title={'center': 'MVC — size=3, valid=True'}>
png

Collections

Generate a benchmark collection of random instances for batch processing.

collection = MinimumVertexCoverCollection.from_random(min_nodes=4, max_nodes=6, num_instances=2, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: minimum_vertex_cover<minimum_vertex_cover>
Minimize
  x_0 + x_1 + x_2 + x_3
Subject To
  edge_0_1: x_0 + x_1 >= 1
  edge_0_2: x_0 + x_2 >= 1
  edge_0_3: x_0 + x_3 >= 1
  edge_2_3: x_2 + x_3 >= 1
Binary
  x_0 x_1 x_2 x_3