Bipartite maximum matching with added constraints

Suppose you have two lists as follows

List $$A$$ = $$(a_1, a_2, ..., a_m)$$

List $$B$$ = $$(b_1, b_2, ..., b_n)$$

Each element in list $$A$$ can be paired with many or no elements in list $$B$$. I have a function $$f(a_i, b_j)$$ that returns true or false depending on whether the match is valid or not. However, if you pair element $$i$$ in list $$A$$ then you also have to pair the $$i$$-th element in list $$B$$. So, for example, the pair can be $$(a_i, b_2)$$ and $$(a_1, b_i)$$ or even $$(a_i, b_i)$$.

I want to find the maximum number of pairings between the two lists with the added constraint of if the $$i$$-th element of list $$A$$ is paired, then the $$i$$-th element of list $$B$$ must also be paired.

My intuition says that modifying the maximal matching bipartite algorithm might be useful for this. However, I am stuck in actually figuring out how to do this. Any help would be appreciated.

• Do you understand under pairings any subset (i.e. relation) of Cartesian product? I mean, that, if, for example we have not your restriction, then in Cartesian product of 2 lists are $n\cdot m$ different pairs, so we can consider $2^{n\cdot m}-1$ different non empty pairings - are you agree? – zkutch Sep 22 '20 at 1:10
• This is not a matching. In a matching, each node is paired with at most one node. – xskxzr Sep 22 '20 at 10:40

1 Answer

Let me start by modifying the problem statement to use standard graph theory terminology, according to my interpretation of the original post:

Let $$G=(V, E)$$ be a bipartite graph, with $$V= A \cup B$$, with $$A=\{a_i\}_{1\leq i \leq m}$$, with $$B=\{b_j\}_{1 \leq j \leq n}$$, and with $$E \subseteq A \times B$$. For an edge set $$S \subseteq E$$, let $$f(A, S)$$ denote the set of integers $$i$$ such that $$(a_i, b_k) \in S$$ for some $$k$$, and let $$g(B, S)$$ denote the set of integers $$j$$ such that $$(a_k, b_j)\in S$$ for some $$k$$. Find a maximal edge set $$S^*\subseteq E$$ with the property that $$f(A, S^*)\subseteq g(A, S^*)$$.

Assuming that this interpretation is correct, this algorithm should work:

Initialize $$S = E$$. Construct $$m$$ lists $$A_1, A_2, \ldots A_m$$, where $$A_i = \{j \ |\ (a_i, b_j) \in S\}$$, and construct $$n$$ lists $$B_1, B_2, \ldots B_n$$, where $$B_j = \{i \ |\ (a_i, b_j) \in S\}$$. Compute $$f(A, S)$$ and $$g(B, S)$$, and take some $$c \in f(A, S) - g(B, S)$$. Remove all edges of $$S$$ of the form $$(a_c, b_k)$$, and update $$\{A_i\}, \{B_j\}, f(A,S)$$, and $$g(B, S)$$ accordingly. Repeat until $$f(A, S) - g(B, S)$$ is empty.

It is easy to see that the resultant $$S$$ is maximal, as every edge removed was necessary. It is also easy to see that the running time is $$O(\lvert V \rvert+\lvert E \rvert)$$, as each edge is processed $$O(1)$$ times.

• I don't understand. What do you mean by "all edges excluded by the condition"? The condition (the "added constraint" from the question) doesn't exclude edges, so I don't understand what you are proposing. – D.W. Sep 21 '20 at 5:03
• I don’t think the OP used the term “matching” in the standard graph theoretical sense. “Each element in list A can be paired with many or no elements in list B”. – dshin Sep 21 '20 at 5:09
• @dshin I don't understand how you can remove edges using the "added constraint" stated in the question. – fardeem Sep 21 '20 at 5:24
• I've added some more detail to the answer. – dshin Sep 22 '20 at 2:09