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.


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.


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.