Maximum multi-matching

graph theorymatching-theory

I'm interested in the following variant of classical matching: A multi-matching is a subgraph of a given graph G that consists of disjoint cliques of size 2 or greater. The goal is to find a multi-matching that is maximum, i.e., covers as many vertices as possible.

It clearly suffices to consider only cliques of size 2 or 3, as larger ones could simply be split up. I'm wondering if this is known under some other name, and if any good algorithms or characterizations similar to Berge's Lemma are known for this?

Edit: Example of graph with maximum (multi-)matching:

enter image description here

Best Answer

We can derive a characterization similar to Berge's Lemma in a similar way.
Let $G$ be a graph, and $M$ be a multi-matching (a set of disjoint edges and triangles). Let $M'$ be another multi-matching spanning more vertices. We take the symmetric difference $(M - M′) \cup (M′ - M)$ and look at the connected components.

A key point of Berge's Lemma is that any edge connected to a connected component $C$ of $S$ belongs to none of the matchings, and thus, we can swap all the edges from $C$ independently from the remaining of the graph.
In our case, an edge $e$ connected to C either belongs to none of the matchings or belongs to both of the matchings.
We have the following result :

Lemma 1:
Let $e\in M\cap M'$ be an edge neighbor of $C$. Then $e$ has both extremities in $C$. Moreover, $e$ belongs to a triangle in either $M$ or $M'$.

Proof:
Let $e\in M\cap M'$ be an edge neighbor of $C$. Let $e'\in C$ be an edge neighbor to $e$. We can suppose without loss of generality that $e'\in M$. By necessity, $e'$ and $e$ belongs to a triangle in $M$. Let $e''$ be the third edge of this triangle. $e''\in C$, otherwise, we would have $e''\in M\cap M'$, and as both $e$ and $e''$ would belong to $M'$, we would have $e'\in M'$, which would contradict with $e'\in C$. So $e$ have both extremities in $C$.

Now, let's take a connected component $C$ where $M'$ span more vertices than $M$(there must exist at least one).
We sequentially build a chain-like subgraph as follow :
Start by taking a vertex $v$ of $C$ only spanned by $M'$ (there must exist at least one). Go to STEP 1.

STEP 1 :

  • If $v$ is adjacent to two edges in $M'\cap C$, then it belongs to a triangle of $M'$, and we have two cases:
    • If the third edge belongs to $C$, the full triangle has no overlap with $M$. If we already encountered this triangle, we have a loop, we add this triangle to the chain and we stop the procedure. Else we choose only one of the two edges, we add it to the chain, and continue to STEP 2 with the other extremity of this edge as $v$.
    • If the third edge does not belong to $C$, then it belongs to $M$. Two cases :
      • If this edge forms a triangle in $M$, then we add one of the two edges of $M'$ to the chain, then we add the triangle at the end of the chain, and we stop the procedure.
      • Else, this edge forms a single edge in $M$. We add both edges from $M'$ and this edge from $M$ and we stop the procedure. We call that ending structure a switch.
  • Else $v$ is adjacent to only one edge in $M'\cap C$. This edge can't belong to a triangle in $M'$. We add this edge to the chain and continue to STEP 2 with the other extremity of this edge as $v$.
  • If $v$ is adjacent to no edge in $M'\cap C$, then this vertex is not spanned by $M$. We backtrack to the last choice we made (the only choices are made in STEP 1, whenever there is a full triangle in $M'\cap C$). Note that there is always such a choice, otherwise, $M'$ would not span more vertices than $M$ in the connected component.

STEP 2 :

  • If $v$ is adjacent to two edges in $C\cap M$, then we add the full triangle (whether it is fully included in $C$ or not) and we stop the procedure.
  • If $v$ is adjacent to only one edge of $C\cap M$, this edge can't belong to a triangle in $M$. We add this edge to the chain and continue to STEP 1 with the other extremity of this edge as $v$.
  • If $v$ is adjacent to no edge in $C\cap M$, then this vertex is not spanned by $M$. We stop the procedure.

Finally, we get at the end of the procedure a subgraph composed of an alternating chain, with one extremity not spanned by $M$, and the other extremity is either :

  • another extremity not spanned by $M$
  • a triangle in $M$
  • a switch (two edges not in $M'$ forking at the extremity, and linked by an isolated edge in $M$.
  • a triangle not in $M$, with an alternating chain linking the two other vertices of the triangle. We will call it an ending loop.

In both of these cases, we can do a swap. Let $t$ be the chain obtained after the procedure. Let $e$ be an edge neighbor of $t$.

  • if $e \notin C$
    • if $e$ is adjacent with only one extremity to $C$, then it doesn't belong to $M$ (see lemma 1), so it won't affect the swap.
    • if $e$ is adjacent with both extremities to $C$, then it is part of a triangle in one of the matchings (lemma 1).
      • If it is part of a triangle in $M$, then by construction, it would have been added to $t$, creating an ending triangle.
      • If it is not part of a triangle in $M$, then it is an isolated edge in $M$, and it is part of a triangle in $M'$ (lemma 1). By construction, it would have been added to $t$, creating an ending switch.
  • if $e\in C$, the only way it can't have been added is if it was the not chosen edge at STEP 1 in the case of two leaving edges in $M'$. Thus $e\notin M$ and won't affect the swap. For each case, we can quickly verify that if we swap all edges of $t$ and if the extremity is a switch (resp. a triangle), then we swap it to a triangle (resp. a switch), then it leaves a valid multi-matching spanning more vertices than $M$.

This gives us (by contraposition) the following result:

Lemma 2 (Berge's Lemma for multi-matching)
$M$ is a maximal multi-matching if and only if it has no swap structure. (Where a swap structure is one of the 4 structures aforementioned)

We can now adapt the blossom algorithm to get a polynomial-time algorithm. We search an alternating path similarly, but at each vertex, we first check that we have a loop. If so, we first check if it is closed by a (complemented) triangle, and in that case, we can swap. Otherwise, we apply the contraction of the blossom.
Then we check if we have an ending structure (free vertex, triangle, or switch). If so, we can swap. If we find a switch, as we have checked two further vertices, we must check beforehand that we didn't form a loop. If so, we have an odd cycle and we can contract it in a blossom (finding a triangle can't result in a loop).
We need some extra care. A contracted vertex can't be involved in an ending triangle. If a contracted vertex is involved in a switch or at the bifurcation of an ending loop, we need to first unwrap the contracted vertex. Then either we can do the swap, or we can contract the ending structure in a contracted vertex. (both the switch and the ending loop contain an odd cycle). If we find a blossom, but the linking vertex is a contracted one, we need to first unwrap it to see if the loop created is an ending loop. These further checks maintain the polynomial claim, as they always result in either a swap or a new blossom.

Related Question