Bipartite matching with a pairwise constraint

Question

A long time ago I remember seeing a very clever construction for the following problem, but I can't find a reference for it anywhere: suppose I have a bipartite graph $G=(U\cup V, E)$, and the vertices of $U$ are grouped into consecutive pairs $(u_1, u_2)$, $(u_3, u_4)$, and so on up to $(u_{n-1}, u_n)$ (so $n$ is even). There was apparently a way to find a maximum matching of $G$, subject to an additional constraint that for each pair $(u_i, u_{i+1})$, either both elements were matched, or neither one was matched. Has anyone seen this problem in the literature, or has an idea of a solution for it?

Answer 1

Here's an approach based on https://math.stackexchange.com/questions/2268922/maximum-2-to-1-matching-in-a-bipartite-graph

You can formulate the problem as perfect matching in a non-bipartite graph $G' = (U \cup V \cup W, E')$ defined as follows. Fix $k\in\{0,1,\dots,|V|\}$, let $W=\{w_1,\dots,w_k\}$, and let $$E' = E \cup \{(u_1,u_2),\dots,(u_{n-1},u_n)\} \cup (V \times W).$$

Let $M$ be a perfect matching in $G'$, if one exists. If $(u_{2i-1},u_{2i})\in M$, then neither $u_{2i-1}$ nor $u_{2i}$ is matched in $G$. If $(u_{2i-1},u_{2i})\not\in M$, then both $u_{2i-1}$ and $u_{2i}$ are matched in $G$. The nodes in $W$ are there to allow the nodes in $V$ to be matched exactly once in $G'$ if they are unmatched in $G$. The largest constrained matching in $G$ corresponds to the smallest $k$ that yields a perfect matching in $G'$.