# (C) Quantum Computing Inc., 2026.
from typing import Dict, List, Tuple
import numpy as np
import networkx as nx
from eqc_models.base.quadratic import ConstrainedQuadraticModel
[docs]
class VertexCoverModel(ConstrainedQuadraticModel):
"""
Minimum vertex cover as a constrained quadratic model.
Binary decision variables x_v in {0, 1} indicate whether node v is in
the cover. The objective minimizes the cover size:
min sum_{v in V} x_v
For every edge (u, v) in E, the cover requirement x_u + x_v >= 1 ensures
at least one endpoint is in the cover. Each inequality is converted to an
equality with a binary slack variable s_e per edge e = (u, v):
x_u + x_v - s_e = 1, s_e in {0, 1}
A valid vertex cover exists iff all edge constraints can be satisfied;
the optimum minimizes the number of selected nodes.
"""
def __init__(self, G: nx.Graph):
self.G = G
self.node_map = list(G.nodes)
self.edge_map = list(G.edges)
n = len(self.node_map)
m = len(self.edge_map)
N = n + m
# constraints: x_u + x_v - s_e = 1 for each edge e
A = np.zeros((m, N), dtype=np.float32)
b = np.ones((m,), dtype=np.float32)
node_index = {u: i for i, u in enumerate(self.node_map)}
for k, (u, v) in enumerate(self.edge_map):
A[k, node_index[u]] = 1.0
A[k, node_index[v]] = 1.0
A[k, n + k] = -1.0
# objective: linear cardinality on x variables; slacks have weight 0
h = np.zeros((N,), dtype=np.float32)
h[:n] = 1.0
J = np.zeros((N, N), dtype=np.float32)
ConstrainedQuadraticModel.__init__(self, h, J, A, b)
self.upper_bound = np.ones((N,), dtype=np.float32)
@property
def variables(self) -> List[str]:
""" Variable names: x_<node> for each node, then s_<edge_index> per edge. """
names = [f"x_{u}" for u in self.node_map]
names.extend([f"s_{k}" for k in range(len(self.edge_map))])
return names
[docs]
def decode(self, solution: np.ndarray) -> np.ndarray:
""" Threshold the first n entries to obtain a binary cover indicator vector. """
n = len(self.node_map)
decoded = np.zeros_like(solution, dtype=np.int32)
decoded[:n] = (np.asarray(solution[:n]) > 0.5).astype(np.int32)
return decoded
[docs]
def cover(self, solution: np.ndarray) -> Dict:
""" Return a dictionary mapping each node to its cover indicator (0 or 1). """
n = len(self.node_map)
return {self.node_map[i]: int(solution[i] > 0.5) for i in range(n)}
[docs]
def getCoverNodes(self, cover: Dict) -> List:
""" Return the list of nodes selected in the cover. """
return [u for u in self.node_map if cover[u] == 1]
[docs]
def getCoverSize(self, cover: Dict) -> int:
""" Number of nodes in the cover. """
return sum(1 for u in self.node_map if cover[u] == 1)
[docs]
def getUncoveredEdgeCount(self, cover: Dict) -> int:
""" Count edges with neither endpoint in the cover. """
return sum(1 for u, v in self.G.edges if cover[u] == 0 and cover[v] == 0)
[docs]
def isValidCover(self, cover: Dict) -> bool:
""" True iff every edge has at least one endpoint in the cover. """
return self.getUncoveredEdgeCount(cover) == 0
[docs]
def costFunction(self) -> Tuple[np.ndarray, np.ndarray]:
""" Return the linear and quadratic pieces of the cardinality objective. """
return self.linear_objective, self.quad_objective
@property
def constraints(self):
""" Return LHS, RHS in numpy matrix format. """
return self.lhs, self.rhs
@property
def objective(self):
""" Linear objective vector (cardinality on x, zeros on slacks). """
return self.linear_objective