4
$\begingroup$

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 \}$

$\endgroup$
11
  • $\begingroup$ You have written " The question is what is minimal size of set V so that perfect matching exists". Isn't it always exist? $\endgroup$ – pointer Jun 1 '14 at 16:04
  • $\begingroup$ 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? $\endgroup$ – Thomas Andrews Jun 1 '14 at 16:05
  • $\begingroup$ @ThomasAndrews I edited and added an example. $\endgroup$ – Ashot Jun 1 '14 at 16:16
  • $\begingroup$ 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. $\endgroup$ – pointer Jun 1 '14 at 16:17
  • $\begingroup$ @user121270 You are right, minimum set cover is NP-hard $\endgroup$ – alejopelaez Jun 1 '14 at 16:18
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Why must every number be in at least 3 left components? It may be in only one left component that is paired with 3 right components which cover right set. $\endgroup$ – Ashot Jun 2 '14 at 7:36
  • $\begingroup$ It's mean it's in at least $3$ "left component" sets. $\endgroup$ – pointer Jun 2 '14 at 7:57
  • $\begingroup$ Ok, Now I understand, Thank you. $\endgroup$ – Ashot Jun 2 '14 at 8:02
  • $\begingroup$ You're welcome. $\endgroup$ – pointer Jun 2 '14 at 8:03

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.