0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – zkutch Sep 22 at 1:10
  • $\begingroup$ This is not a matching. In a matching, each node is paired with at most one node. $\endgroup$ – xskxzr Sep 22 at 10:40
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Sep 21 at 5:03
  • $\begingroup$ 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”. $\endgroup$ – dshin Sep 21 at 5:09
  • 1
    $\begingroup$ @dshin I don't understand how you can remove edges using the "added constraint" stated in the question. $\endgroup$ – fardeem Sep 21 at 5:24
  • $\begingroup$ I've added some more detail to the answer. $\endgroup$ – dshin Sep 22 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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