In the reduction from Vertex Cover problem to Dominating Set a new vertex is added for each edge in the original graph. Specifically, Given graph $G=(V,E)$ where $|V|=n$ with $VC$ with size $k$ we construct a new graph $G'=(V',E')$ where $n\le |V'| \le n^2$ which has a $DS$ of size $k$ as well. The bounds are for the edge cases where $G$ has no edges and when it's a "full graph".

Consider the Vertex Cover & Dominating Set gap problem. I'm interested in proving the following: $$Gap[\alpha n,\beta n]-VC \le Gap[\alpha' n,\beta' n]-DS$$

Note that $n$ in the two problems might be different as stated above.

The same reduction works, but I'm not sure regarding the choice of $\alpha'$ and $\beta'$. Consider the completeness argument. Say $G$ has a $VC$ with size at least $\beta n = k$ (a "yes" instance), then $G'$ has a $DS$ with a size at least $k=\beta' n' = \beta' (n+n^2) \rightarrow \beta' = \frac {1}{n+1}\beta$.

It doesn't make sense that $\beta'$ is dependent on $n$, because that loses the whole point of gap reductions. What am I missing?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.