4
$\begingroup$

Let $G(V_1, V_2, E)$ be a bipartite graph such that degree of all the vertices in $V_1$ is bounded by some constant (say) $d$. Now, for given two positive integer $l$ and $k$, we wish to decide if there is a vertex cover $A\cup B$ with $|A|\leq l$ and $|B|\leq k$, where $A\subseteq V_1, B \subseteq V_2.$

Now, I have following two questions:

1) What is the complexity of the above problem when both $k$ and $l$ are part of input. (Intuitively, it appears to be hard.) If it is hard, then is there any PTAS known to approximate the problem.

2) What is the complexity of the problem when one of the parameters $k$ or $l$ is constant?

Pls let me know if there is any doubt about the problem.

$\endgroup$
  • $\begingroup$ If the degree of the vertices is unconstrained, then your problem is known to be NP-hard. If you don't know this result, see this paper and the references therein. informatik.uni-trier.de/~fernau/papers/BaiFer08.pdf $\endgroup$ – Hiroki Yanagisawa Aug 4 '15 at 13:03
  • 2
    $\begingroup$ Surely you can reduce set cover to your problem in a standard way --- given a collection of sets, let $V_1$ contain the sets, let $V_2$ contain the elements, and have edge $(S,e)$ if set $S$ contains element $e$. Add one artificial node $r$ to $V_2$, with edges to all sets. Take $k=1$. Then set covers of size $\ell$ correspond to vertex covers meeting your constraints. $d$ will be the maximum set size; even if $d=4$, the problem is NP-hard e.g. cstheory.stackexchange.com/questions/191/… . $\endgroup$ – Neal Young Aug 4 '15 at 17:58
3
+50
$\begingroup$

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.

$\endgroup$

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.