A variation of the maximum bipartite matching problem

Question

Given a bipartite simple graph $G=(V,E)$, where $V=A\cup B$ and $A\cap B=\emptyset$, any edge in $E$ connects two vertices in $A$ and $B$, respectively. The maximum bipartite matching problem is to find the largest subset $E'\subseteq E$ such that no two edges in $E'$ share common vertices. We know that this can be addressed in $O\left(\sqrt{|V|}|E|\right)$ time. Now there is a variation. Each vertex in $A$ has exactly two edges connected with some vertex in $B$. We restrict each vertex in $A$ to be either unmatched, or matched with exactly two vertices in $B$. Each vertex in $B$ can only match at most one vertex in $A$. The question is: how many vertices in $A$ can be matched at most?

I've considered reducing this problem to max flow. I set up a super source $s$ and a super sink $t$. $s$ connects to all vertices in $A$, with the capacity of the edges being $2$. $t$ connects to all vertices in $B$, with the capacity of the edges being $1$. The edges between $A$ and $B$ have capacity $1$, and they're added according to the edge set $E$. Now the answer of the question is the max flow of the graph divided by $2$. But in this way, I can't restrict each vertex in $A$ not to match only one vertex in $B$. So it doesn't work.

My question is: Can this problem be reduced to some problem known to be in $\mathbf{P}$?

Background: This problem is derived from a "string merging" game. Let there be $m$ distinct strings with length $n$, and each string consists of $0$, $1$. If there is one and only one corresponding character in two strings being complement (i.e. $0$ and $1$), we can merge the two strings into a new string with the character replaced by $x$. For example, $10\color{green}{1}11$ and $10\color{green}{0}11$ can be merged into $10\color{blue}{x}11$. Each string can only be used once, and new strings cannot be furthur merged. Now given $m$ of such strings, the goal of the game is to merge them into as fewer strings as we can. However, one string can be merged with many strings, so we need to find out the most clever way.

Here is another example. Consider four strings:

(a) 0110
(b) 0010
(c) 0000
(d) 1000

(a), (b) can be merged into $0x10$, (b), (c) can be merged into $00x0$, and (c), (d) can be merged into $x000$. There are two strategies to perform merging: the first way is to merge (a), (b) and (c), (d), then we'll get two strings. The second is to merge (b), (c), but (a) and (d) cannot be merged, so we'll get three strings. Apparently the first strategy is more clever. Then the question is: what is the most clever way?

I've reduced the problem into a graph theory problem. Let the new strings form set $A$ and the original strings from set $B$. The vertex of the new string is connected to the two strings merged into it. Then the problem is to find the maximum match as I mentioned.

Answer 1

Yes, the problem is in $\mathbf{P}$. For every vertex $u\in A$, let $M(u)$ be the set of the two vertices in $B$ that is connected with $u$. For every vertex $v\in B$, let $N(v)=\{u\in A|(u,v)\in E\}$. We construct another undirected graph $G'=(V',E^*)$, whose vertex set is $V'=B$. For every $v_1,v_2\in B\,(v_1\ne v_2)$, we let $(v_1,v_2)\in E^*$ if and only if $\exists u\in A$ such that $M(u)=\{v_1,v_2\}$. Now each (effective) $u\in A$ is converted to an $e^*\in E^*$ (for multiple $u$ that share common $M(u)$, we only take one of them). In $G$ we require that each vertex $v\in B$ can only match at most one $u\in A$, so equivalently we require every $e^*\in E^*$ we selected does not share a common vertex. Now the problem becomes the maximum matching problem, which can be addressed in $O\left(|E^*|{|B|}^2\right)$ time using the blossom algorithm.

For the version of the "string merging" game, actually, the graph $G'$ is a bipartite graph and hence the problem can be solved with the Hopcroft-Karp algorithm. We can consider it in the following way. For two strings $s_1, s_2$, if they can be merged, we denote $g(s_1,s_2)$ as the specific position being merged. For example, $g(00\color{green}{1}1,00\color{green}{0}1)=3$, since the third characters in the strings are merged. The method to build $G'$ is as follows. Each string is equivalent to a vertex $v\in B$, so $B$ is simply the string set. We define $(s_1,s_2)\in E^*$ iff the two strings $s_1,s_2$ can be merged. We now show that any cycle in $G'$ contains even amount of vertices (strings). Let $C$ be a cycle and $V(C)$ be its vertex set. We assert that if $s_1,s_2\in V(C)$ and $g(s_1,s_2)=p$, then there must be $s_3,s_4\in V(C)$ such that $\{s_1,s_2\}\cap\{s_3,s_4\}=\emptyset$ and $g(s_3,s_4)=p$. This is easy to understand. We take a tour along $C$: $s_1\to s_2\to \cdots\to s_1$. Note that when the $p$-th character alters, the two adjacent strings can be merged. Now $s_1\to s_2$ is just an example of such situation. Without losing generality, lets say the $p$-th character in $s_1$ is $0$ (written as $s_1[p]=0$). Then we must have $s_2[p]=1$. Now since the destination of our tour is $s_1$, the $p$-th character transform from $1$ to $0$ along the tour. When it transforms, we found $s_3$ and $s_4$. By this approach we can prove that the graph $G'$ is a bipartite graph.