Let $N$ be the number of vertices and $M$ the number of edges in $G$.
Decision variables¶
Let each of $M$ binary variables $q$ correspond to each edge of $G$ to indicate whether the maximal
matching $D$ contains the edge. $q=1$ if included in $D$, $0$ if not.
For example, for the following maximal matching, the binary variable $q$ would be as in the table
below.
| Edge $(u, v)$ |
$$(0, 1)$$ |
$$(0, 5)$$ |
$$(1, 2)$$ |
$$(1, 5)$$ |
$$(2, 3)$$ |
$$(2, 4)$$ |
$$(3, 4)$$ |
$$(4, 5)$$ |
| $$q$$ |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
Objective function¶
Since the number of elements in $D$ should be as small as possible, we minimize $ \displaystyle
\sum_{i =
0}^{M - 1} q_i$.
Constraints¶
As explained earlier, $D$ being a maximal matching means that the following constraints are satisfied
($D$ is the subset of edges in $G$).
- Condition 1: Edges contained in $D$ are not adjacent to each other.
- Condition 2: Edges not included in $D$ are always adjacent to one of the edges in $D$.
Let us rephrase these conditions and express them in terms of $q$.
First, we can rephrase condition 1 as "no two adjacent edges are both contained in $D$":
$$
q_{v, u} q_{v, w} = 0 \quad \text{for} \quad (v, u), (v, w) \in E
$$
Here, the element of the binary variable array $q$ corresponding to the edge $(u, v)$ is written as
$q_{u, v}$. Also, $E$ denotes the edge set of $G$.
Next, we can rephrase condition 2 as "every edge of $G$ is necessarily adjacent to one of the edges
of
$D$". We can further rephrase this as "for any edge $(u, v)$ of $G$, either $u$ or $v$ is an endpoint
of
one of the edges of $D$". We can determine whether a vertex $v$ is an endpoint of any edge of $D$ by
whether the sum of the corresponding binary variables is $1$ or $0$ for all edges out of $v$. So the
condition 2 is:
$$
(1 - \sum_{(v, x) \in E} q_{v, x}) (1 - \sum_{(u, y) \in E} q_{u, y}) = 0 \quad \text{for} \quad (u,
v)\in
E.
$$
