Source code for eqc_models.graph.vertexcover

# (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