Maximal Matching in a constrained, unweighted Bipartite Graph

Question

Suppose a set of partially connected nodes:

• All nodes are in set A xor in Set B (i.e. Bipartite Graph)
• All nodes have a datetime property.
• Connections in the Bipartite Graph exist if-and-only-if the (absolute) difference in datetime < limitValue (and the Nodes are in opposing sets, obviously)
• Nodes and Connections have no other relevant properties (weights, directions, etc.)

Goal: Find a maximal Matching of the Nodes.

---

Hypothesis:

Whilst a normal BPG requires Ford-Fulkerson or similar to find a Maximal Matching, I suspect that a simple Greedy algorithm is sufficient to optimise this scenario, because the rules for connections exclude the sorts of situations that would break a Greedy approach.

Specifically, I think you can just order all the nodes, and then walk up the list pairing adjacent opposite-set nodes, whenever you pass them.

Is this correct? If so, how would one go about proving it?

Answer 1

Let $I, J$ be the two sets of nodes and let both be sorted by their datetime. Let $E$ be the set of valid edges. For each $i\in I$ let $D_i$ be the neighbours of $i$. Your proposed greedy algorithm will then do the following.

M = {}
Q_I = {}
Q_J = J
for i in I ascending:
   if empty(intersection(D_i,Q_J)):
      Q_I.append(i)
   else:
      j = min(intersection(D_i,Q_J))
      M.append((i,j))
      Q_J.remove(j)
return M

Then $M$ is a maximal matching. The proof uses that a matching in a bipartite graph is maximal iff there is no augmenting path.

Assume there was an augmenting path. Let $P$ be an augmenting path of minimal length. Let $i$ be the smallest appearing node from set $I$ in $P$.

Case 1: $i$ has only one adjacent edge $(i,j)$ in $P$. This would imply $i\in Q_I$ as $P$ is an augmenting path. But as the neighbour $i'$ of $j$ in $M$ is bigger than $i$, $j$ would have still been in $Q_J$ at the point where the algorithm considered $i$, which is a contradiction to $i\in Q_I$.

Case 2: $i$ has two adjacent edges $(i,j), (i,j')$ in $P$ and let $(i,j)\in M$. Then by the choice of the neighbouring edge in the algorithm $j<j'$. Let $(i',j)$ be the next edge following $j$ in $P$. As $j'>j$, $i'>i$ and $(i',j)\in E$ by your daytime property also $(i',j')\in E$. But then removing $(i',j), (i,j), (i,j')$ from $P$ and adding $(i',j')$ would also be an augmenting path contradicting the minimality of $P$.