Max Vertex Cover
import networkx as nx import pyomo.core as pyo def mvc(graph: nx.Graph, k: int) -> pyo.ConcreteModel: model = pyo.ConcreteModel() model.x = pyo.Var(graph.nodes, domain=pyo.Binary) model.amount_constraint = pyo.Constraint(expr=sum(model.x.values()) == k) def obj_expression(model): # number of edges not covered return sum((1 - model.x[i]) * (1 - model.x[j]) for i, j in graph.edges) model.cost = pyo.Objective(rule=obj_expression, sense=pyo.minimize) return model
This function generates a PYOMO model which formulates the Max k-Vertex Cover. Here, we search for a set of k vertices that cover the most edges in the graph. The model consists of:
- Index set declarations (model.Nodes, model.Arcs)
- Binary variable declaration for each node (model.x) indicating whether the variable is chosen to the set
- Constraint rule – ensure that the set is of size k.
- Objective rule – count the number of edges not covered. i.e. both related variables are zero.