The following is a list of results I'm going to prove:
- if $k$ and $l$ are parts of the input and $d = 1$ is a fixed constant then the problem is polynomial time solvable
- if $k$ and $l$ are parts of the input and $d \ge 2$ is a fixed constant then the problem is NP-complete
- if $k$ is a fixed constant then the problem is polynomial time solvable
- if $l$ is a fixed constant then the problem is polynomial time solvable
The first two bullet points address question number 1 and the last two address question number 2.
lemma: if we know $A \subseteq V_1$ with $|A| \le l$ (or $B \subseteq V_2$ with $|B| \le k$), we can decide in polynomial time whether there exists $B \subseteq V_2$ with $|B| \le k$ (resp $A \subseteq V_1$ with $|A| \le l$) such that $A \cup B$ is a vertex cover
For the proof of this lemma, we do not use the constraint that vertices in $V_1$ have degree at most $d$. Therefore, the situation is symmetric in the two parts of the bipartite graph, and we can restrict our attention to just one part of this lemma: we wish to show that if $A \subseteq V_1$ with $|A| \le l$ then we can decide in polynomial time whether there exists $B \subseteq V_2$ with $|B| \le k$ such that $A \cup B$ is a vertex cover.
Let $B' = \{v \in V_2 | \exists x \in V_1 \backslash A \text{ s.t. } (x, v) \in E\}$.
Suppose that for some $b \in B'$, it is the case that $b$ is not in $B$. By definition of $B'$, there exists an $x \in V_1 \backslash A$ such that $(x,b) \in E$. Then that edge has $x \in V_1$ with $x \not\in A$ and $b \in V_2$ with $b \not\in B$, so $A \cup B$ is not a vertex cover.
Thus in order for $A \cup B$ to be a vertex cover, it must be that $B' \subseteq B$.
Next suppose $B' \subseteq B$. Then consider any $(x, v) \in E$. If $x \in A$ then this edge is covered. If $x \not \in A$ then $v \in B'\subseteq B$ by definition of $B'$, so again the edge is covered. Thus $A \cup B$ is a vertex cover.
So $A \cup B$ is a vertex cover if and only if $B' \subseteq B$. Then there exists a $B$ with $|B| \le k$ such that $A \cup B$ is a vertex cover if and only if $|B'| \le k$.
So in order to decide whether there exists a $B$ with $|B| \le k$ such that $A \cup B$ is a vertex cover, all we have to do is compute $|B'|$ and compare with $k$. This can be done in polynomial time.
If $k$ and $l$ are parts of the input and $d = 1$ is a fixed constant then the problem is polynomial time solvable
Begin by removing all vertices of degree zero since the presence or absence of those vertices in a set does not affect whether that set is a vertex cover.
Since $d = 1$, we see that in the remaining graph, every element of $V_1$ has exactly one neighbor. We can conclude that $G$ has $|V_2|$ connected components, each of which consists of one element of $V_2$ together with all of its neighbors in $V_1$.
We wish to know whether it is possible to construct a vertex cover $A \cup B$ with $A \subseteq V_1$ and $B \subseteq V_2$ where $|A| \le l$ and $|B| \le k$.
Each connected component of the graph provides a choice: either $B$ must contain the element of $V_2$ in that component or $A$ must contain each element of $V_1$ from that component.
Then in order to minimize the size of $A$ while maintaining $|B| \le k$, it is clearly optimal to choose $B$ such that it contains the elements of $V_2$ with largest degree.
Since we know the optimal value of $B$ (in polynomial time), we can apply the lemma to solve the problem in polynomial time.
If $k$ and $l$ are parts of the input and $d \ge 2$ is a fixed constant then the problem is NP-complete
First note that the problem is clearly in NP since the set $A \cup B$ forms a certificate. Thus we must simply prove the problem NP-hard in order to show NP-completeness.
We do this by reduction from the clique problem.
Suppose we are given a clique instance in the form of a graph $G' = (V', E')$ and a value $k'$. This instance is a yes instance if and only if there exists a clique in $G'$ of size $k'$.
Then we construct an instance of our problem consisting of $G = (V_1, V_2, E)$, $k$, and $l$ as follows:
- $V_1 = E'$
- $V_2 = V'$
- $E = \{(e, v) \in E' \times V'| v \text{ is an endpoint of } e\}$
- $l = |E'| - \frac{k'(k' - 1)}{2}$
- $k = k'$
Note that each element of $V_1$ has exactly two neighbors (which is ok since $d \ge 2$).
This reduction is clearly polynomial time, since each part of the output instance can be computed from the input instance very quickly.
Suppose the input instance in a yes instance. Then let $B$ be a clique in $G'$ of size $k'$ (which exists since the input instance is a yes instance). Let $A \subseteq E'$ contain those edges of $G'$ which are not in the clique $B$. There are $\frac{k'(k' - 1)}{2}$ edges in the clique, so $|A| = |E'| - \frac{k'(k' - 1)}{2}$.
Thus we have found $A \subseteq V_1$ and $B \subseteq V_2$ with $|A| \le l = |E'| - \frac{k'(k' - 1)}{2}$ and $|B| \le k = k'$. The only thing left to do in order to show that the output instance is a yes instance is to show that $A \cup B$ is a vertex cover.
So consider any edge $(e, v) \in E$ (where $e \in V_1 = E'$ and $v \in V_2 = V'$). If $e \in A$ then the edge is covered. If $e \not\in A$ then $e$ must by one of the edges in the clique $B$ (in graph $G'$). By the definition of $E$, $v$ is an endpoint of $e$ (which is an edge in the clique $B$). Thus $v \in B$ and again the edge $(e, v)$ is covered. We see that $A \cup B$ is a vertex cover.
We showed above that if the input instance is a yes instance, so is the output instance.
Now suppose that the input instance is not a yes instance. Suppose we have $A \subseteq V_1$ with $|A| \le l = |E'| - \frac{k'(k' - 1)}{2}$ and $B \subseteq V_2$ with $|B| \le k = k'$. Since the input is not a yes instance, there is no clique in $G'$ of size $k'$; therefore fewer than $\frac{k'(k' - 1)}{2}$ edges in $G'$ have both endpoints in $B$. Then since $V_1 \backslash A = E' \backslash A$ contains at least $\frac{k'(k' - 1)}{2}$ elements, each of which is an edge of $G'$, we conclude that at least one edge in $E' \backslash A$ has an endpoint not in $B$.
Let $e = (w, v)$ be an edge in $E'$ with $e \not\in A$ and $v \not\in B$. Then the edge $(e, v)$ (which is in $E$ by the definition of $E$) is not covered, and so $A \cup B$ is not a vertex cover.
We see then that in the case that the input instance is a no instance, the answer to the output instance is no as well.
We showed above that the reduction is polynomial time and answer preserving. Since the input problem (clique) is NP-hard, the output problem is NP-hard as well.
If $k$ is a fixed constant then the problem is polynomial time solvable
The number of sets $A$ with $|A| \le k$ is $|A| \choose kl$, which is polynomial in the size of the input since $k$ is a fixed constant.
Furthermore, these sets are easily enumerable.
For each candidate value of $A$, we simply apply the lemma to determine whether there exists a corresponding value of $B$ such that $A \cup B$ solves the problem.
If a solution is found, the answer to the overall problem is yes, and if no solution is found, the answer to the overall problem must be no.
If $l$ is a fixed constant then the problem is polynomial time solvable
The number of sets $B$ with $|B| \le l$ is $|B| \choose l$, which is polynomial in the size of the input since $l$ is a fixed constant.
Furthermore, these sets are easily enumerable.
For each candidate value of $B$, we simply apply the lemma to determine whether there exists a corresponding value of $A$ such that $A \cup B$ solves the problem.
If a solution is found, the answer to the overall problem is yes, and if no solution is found, the answer to the overall problem must be no.
