# Bipartite graph matching like problem.

Let $A=\{a_1,a_2, ..., a_n \}$ and $B=\{b_1,...,b_m\}$ be finite sets. Also $A_1,...,A_k\subset A$ are covering of $A$ and $B_1,...,B_t\subset B$ are covering of $B$. Let $V$ be a set of pairs of $A_xB_y$ so that for each $a_i\in A$ and $b_j \in B$ there is a $A_xB_y$ pair in $V$ and $a_i \in A_x,b_j\in B_y$.

This is similar to perfect matching in bipartite graphs but instead of single vertex we take some set of verticies and match them another set. The question is what is minimal size of set $V$ so that perfect matching exists. We can take all $A_i$ and $B_j$ and since they are covering we will have the condition satisfied. But is will use $tk$ pairs.

Do anyone know some theory about this problem? I am thinking this may be reduced to bipartite graph matching problem. I need algorithm of finding minimal set $V$.

He is example:

Let $A=B=\{0,1,2\}$

$A_1=B_1=\{0,1\}$

$A_2=B_2=\{0,2\}$

$A_3=B_3=\{1,2\}$

If we take $V=\{A_1A_1,A_1A_2, A_2A_1,A_2A_2 \}$ the condition will be satisfied. All pairs will be covered.

$(0,0)\in A_1A_1$

$(0,1)\in A_1A_1$

$(0,2)\in A_1A_2$

$(1,0)\in A_1A_1$

$(1,1)\in A_1A_1$

$(1,2)\in A_1A_2$

$(2,0)\in A_2A_1$

$(2,1)\in A_2A_1$

$(2,2)\in A_2A_2$

You can see that $V=\{A_1A_2, A_2A_3, A_3A_1\}$ is the answer.

From comments it turned out that this problem is NP-hard so I am adding some conditions to get answer of my original problem.

Let $A=B$ and all $A_i$ have the same size. If we add this conditions it may be possible to give upper bound for $V$. In fact I am trying to get minimal cover of following graph:

Consider vector space $F_2^3$

$A=B=\{(000), (001), (010), (011), (100), (101), (110)\}$

$A_i$ is solution of equation. It is coset and contains $4$ vectors.

$A_1=\{x_1=0\}=\{(000), (001), (010), (011)\}$

$A_2=\{x_2=0\}$

$A_3=\{x_3=0\}$

$A_4=\{x_1+x_2=1\}$

$A_5=\{x_2+x_3=1\}$

$A_6=\{x_1+x_3=1\}$

$A_7=\{x_1+x_2+x_3=0\}$

I have showed that covering with size $6$ exists and need help to prove that it is minimal. Here is covering:

$V=\{A_7A_3, A_3A_4, A_5A_1, A_2A_5, A_1A_7, A_7A_2 \}$

• You have written " The question is what is minimal size of set V so that perfect matching exists". Isn't it always exist? Jun 1, 2014 at 16:04
• I find the first paragraph opaque. Perhaps don't use $i$ and $j$ both for indices for the $A_i,B_j$ and $a_i,b_j$, since they don't have the same sizes? Jun 1, 2014 at 16:05
• @ThomasAndrews I edited and added an example. Jun 1, 2014 at 16:16
• I think if you find minimal covering of $A$ and minimal covering of $B$ you can find minimal set $V$. But as I know (maybe I'm wrong) it can't be solved in polynomial time. Jun 1, 2014 at 16:17
• @user121270 You are right, minimum set cover is NP-hard Jun 1, 2014 at 16:18

Let's write $A_i$ as sets of numbers: $$A_1=\{0,1,2,3\}\\ A_2=\{0,1,4,5\}\\ A_3=\{0,2,5,6\}\\ A_4=\{2,3,4,5\}\\ A_5=\{1,2,5,6\}\\ A_6=\{1,3,4,6\}\\ A_7=\{0,3,5,6\}\\$$ (I hope I have calculated everything right:)). It's easy to see that $A_i \cup A_j\ne A$, so every number must be in at least $3$ "left component" sets, so if number of pairs is $k$ we have $$4k\ge21$$ so $k\ge6$.
• It's mean it's in at least $3$ "left component" sets. Jun 2, 2014 at 7:57