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