1
$\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$
2
  • $\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, 2020 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, 2020 at 10:40

1 Answer 1

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.

$\endgroup$
4
  • $\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, 2020 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, 2020 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, 2020 at 5:24
  • $\begingroup$ I've added some more detail to the answer. $\endgroup$
    – dshin
    Sep 22, 2020 at 2:09

Your Answer

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

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