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 that formulates the Max k-Vertex Cover. In this problem, we search for a set of k vertices that cover the most edges in the graph. The model contains:

• Index set declarations (model.Nodes, model.Arcs)
• Binary variable declaration for each node (model.x) indicating whether the variable is chosen for 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.