Minimum Maximal Matching Problem

A matching in an undirected graph is a set of edges such that no two edges share a common endpoint. A maximal matching is a matching to which no additional edge can be added without violating the matching condition. Given an undirected graph $G=(V,E)$, the minimum maximal matching problem asks for a maximal matching $S \subseteq E$ with the minimum number of edges.

The maximality condition of a matching can be described in a compact way. For a node $u\in V$, let $N(u)$ denote the set of edges in $S$ incident to $u$. Then $S$ is a maximal matching if and only if, for every edge $(u,v)\in E$, the following condition holds:

\[1 \leq |N(u)|+|N(v)| \leq 2\]

This condition is satisfied if and only if $S$ constitutes a maximal matching. To ensure that $S$ is a maximal matching, the following cases cover all possibilities:

The solution of the maximum matching problem.

We can formulate the minimum maximal matching problem as finding a subset $S$ that satisfies the above condition and has minimum cardinality.

For a formal proof, see the following paper:

Reference: Nakahara, Y., Tsukiyama, S., Nakano, K., Parque, V., & Ito, Y. (2025). A penalty-free QUBO formulation for the minimum maximal matching problem. International Journal of Parallel, Emergent and Distributed Systems, 1–19. https://doi.org/10.1080/17445760.2025.2579546

QUBO formulation for the minimum maximal matching

Assume that the graph has $n$ vertices and $m$ edges, and that the edges are labeled $0,1,\ldots,m-1$. We introduce $m$ binary variables $x_0, x_1, \ldots, x_{m-1}$, where $x_i=1$ if and only if edge $i$ is selected (i.e., belongs to $S$). The objective is to minimize the number of selected edges:

\[\begin{aligned} \text{objective} &= \sum_{i=0}^{m-1} x_i . \end{aligned}\]

To enforce the maximality condition, we use the following constraint:

\[\begin{aligned} \text{constraint} &= \sum_{(u,v)\in E} (1 \leq |N(u)|+|N(v)| \leq 2) \end{aligned}\]

We construct a QUBO expression $f$ by combining the objective and the constraint as follows:

\[\begin{aligned} f &= \text{objective} + \text{constraint}. \end{aligned}\]

PyQBPP program

The following PyQBPP program finds a minimum maximal matching of a fixed undirected graph with $N=16$ nodes and $M=27$ edges:

import pyqbpp as qbpp

N = 16
edges = [
    (0, 1),  (0, 2),  (1, 3),  (1, 4),  (2, 5),  (2, 6),  (3, 7),
    (3, 13), (4, 6),  (4, 7),  (4, 14), (5, 8),  (6, 8),  (6, 12),
    (6, 14), (7, 14), (8, 9),  (9, 10), (9, 12), (10, 11),(10, 12),
    (11, 13),(11, 15),(12, 14),(12, 15),(13, 15),(14, 15)]
M = len(edges)

adj = [[] for _ in range(N)]
for i in range(M):
    adj[edges[i][0]].append(i)
    adj[edges[i][1]].append(i)

x = qbpp.var("x", shape=M)

objective = qbpp.sum(x)

constraint = 0
for u, v in edges:
    t = 0
    for idx in adj[u]:
        t += x[idx]
    for idx in adj[v]:
        t += x[idx]
    constraint += (1 <= t) & (qbpp.same <= 2)

f = objective + constraint

f.simplify_as_binary()
solver = qbpp.ExhaustiveSolver(f)
sol = solver.search()

print(f"objective = {sol(objective)}")
print(f"constraint = {sol(constraint)}")
print("Selected edges:", end="")
for i in range(M):
    if sol(x[i]) == 1:
        print(f" {edges[i]}", end="")
print()

We first define a vector x of M binary variables, and then define objective, constraint, and f based on the formulation above. The Exhaustive Solver is used to find an optimal solution of f. The values of objective and constraint are printed, along with the list of selected edges.

This program produces the following output:

objective = 6
constraint = 0

Thus, $S$ contains 6 edges, forming a minimum maximal matching.

Visualization using matplotlib

The following code visualizes the Min-Max Matching solution. Selected edges in $S$ and all nodes incident to these edges are highlighted in red:

import matplotlib.pyplot as plt
import networkx as nx

G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(edges)
pos = nx.spring_layout(G, seed=42)

matched_nodes = set()
for i in range(M):
    if sol(x[i]) == 1:
        matched_nodes.add(edges[i][0])
        matched_nodes.add(edges[i][1])
colors = ["#e74c3c" if i in matched_nodes else "#d5dbdb" for i in range(N)]
edge_colors = ["#e74c3c" if sol(x[i]) == 1 else "#cccccc"
               for i in range(M)]
edge_widths = [2.5 if sol(x[i]) == 1 else 1.0 for i in range(M)]
nx.draw(G, pos, with_labels=True, node_color=colors, node_size=400,
        font_size=9, edge_color=edge_colors, width=edge_widths)
plt.title("Minimum Maximal Matching")
plt.savefig("minmax_matching.png", dpi=150, bbox_inches="tight")
plt.show()

In the resulting figure, the selected edges in $S$ and all nodes incident to these edges are highlighted in red. We can see that no more edge can be added, and the maximality condition is satisfied.