Hardness and approximation of a problem with a parameter

Question

Let $H$ be a decision problem, where we are given an integer $k$ and some object, say a graph or a formula. We know that $H$ is NP-complete for $k \geq c$, where $c$ is some constant like 3 ($H$ could be $k$-SAT, or $k$-vertex coloring, or something like that).

I have a problem $X$ I think is NP-complete as well, and I want to prove it. $X$ is a graph problem, and it has a parameter $k'$ similarly.

Given an instance of $H$ with parameter $k \geq c$ (for example let's say $c=3$), I can build an instance of $X$ (in polynomial time), where $k' = c+8$. I can now prove two things:

1. If $H$ with $k$ has no solution, $X$ has no solution with $k$. (There might be a solution for $X$ with $k'$, I don't know).
2. If $H$ with $k$ has a solution, $X$ has a solution with $k'$.

To establish hardness for $X$ with $k'$, should I be able to prove in (1) that $X$ has no solution with $k'$ as well? (Or is my current reduction pretty much useless as it is?) If I were able to do that, would my proof also tell me something about the hardness of approximating $X$? $X$ is a minimization problem.

Answer 1

Yes. To show that decision problem Q is at least as hard as decision problem P (via a many-one reduction), you need to prove that a yes-instance for P maps to a yes-instance for Q, and a no-instance for P maps to a no-instance for Q. That's just what the definition of a (many-one) reduction is.

In your case, P = "X has a solution with parameter $k'$" and Q = "H has a solution with parameter $k$". Therefore, the answer to your question is yes: in (1) you need to prove that $X$ has no solution with parameter $k'$. The definition of P needs to be consistent for both kinds of instances, so it has to use the same parameter in both cases.