Dominant subset in bipartite graph NP-complete proof

Question

Let the dominant subset problem (which is known to be NP-complete) be:

Given a graph $G=(V_G,E_G)$ and an integer $k$, is there a subset $W \subset V_G$ with at most $k$ vertex so that any other vertex $u \in V_G \setminus W $ is connected to some $w \in W$?

I am asked to prove that if $G$ is bipartite, it's still NP-complete, and I'm having trouble doing the polynomial reductions: taking an instance of a general graph and an integer $(G,k)$, to a bipartite graph and another integer $(B, k')$ (in polynomial time) so that $G$ has a dominant subset of size $k$ iff $B$ has a dominant subset of size $k'$.

I thought about replacing each edge $e=(u,v)$ in $G$ for a vertex $e'$ connected to $u$ and $v$ in order to create $B$. However, I'm stuck at figuring out the $k'$ that would make the iff true. Maybe I should do that replacement in some edges and not all?

Answer 1

Although the construction you mention is often useful in reducing graph problems to bipartite graphs, in this case it doesn't seem to work. Another common way of constructing a bipartite graph from $G$ is to take copies $A,B$ of $V_G$, so that for each vertex $v \in V_G$ there is a pair of vertices $v_A,v_B$; and draw an edge between $u_A$ and $v_B$ if either $u = v$ or $uv$ is an edge of $G$.

Let $H = (A,B,E)$ be the bipartite graph obtained in this way and let $H'$ be the (still bipartite) graph we get by adding an extra vertex $x$ to $A$, along with edges $xv$ for all $v \in B$. Now you should show that

• there is a smallest dominating set of $H'$ of the form $\{x\} \cup B'$ where $B' \subseteq B$, and
• dominating sets of this form correspond bijectively to dominating sets of $G$. That is, if $\{x\} \cup B'$ dominates $H'$, then the vertex set $V' \subseteq V_G$ corresponding to vertices in $B'$ dominates $G$, and vice versa.