2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Thought to self. Any proof that this algorithm is optimal must make use of the additional constraint, and the additional constraint must counteract whatever makes Greedy insufficient for the general case, so perhaps an avenue of attack is to identify why Greedy is not sufficient for the general case, and see how that interacts with the additional constraint. $\endgroup$
    – Brondahl
    Feb 1, 2022 at 18:56

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.