# Is variable a constant or a parameter

I am working on the $$[1,j]$$-dominating set problem defined in this paper. In section 4, they study the problem complexity on degenerate graphs and prove that the problem is W[1]-hard for the parameter solution size. The reduction follows from a well-known W[1]-hard problem, multicoloured independent set (MCIS). For a parameterised reduction to work, the parameter in the reduced instance ($$k'$$) must be a function of the parameter in the original instance ($$k$$). But, here the parameter $$k'$$ is given to be at most $$2k+j-1$$, so is $$j$$ in the $$[1,j]$$-domination problem constant?

• Does this answer your question? Role of a variable in problem definition in time complexity
– user16034
Aug 4, 2023 at 6:49
• No, I want to know whether $j$ in the problem defined in the paper is considered to be a constant or not. Since I am working on the same problem, this would help me. @YvesDaoust Aug 4, 2023 at 9:51
• As long as it is mentioned in the problem name, it can be considered as a constant. Aug 4, 2023 at 11:46
• @NarekBojikian That's not correct. You need to take into account that they are looking for parameterized reductions. Aug 4, 2023 at 12:50
• But then they can just exclude it from the name of the problem and consider it as a parameter (usually given in unary encoding, as a part of the input) Aug 4, 2023 at 12:56

It can be considered constant as long as it is mentioned in the problem name. The intuition behind this is that since $$j$$ is in the name of the problem, different values of $$j$$ imply different problems, and hence, we can design a different algorithm for each, i.e. the algorithm itself can depend on $$j$$.
Note that here it is quite important to consider $$j$$ as constant and consider other parameters, since the problem is clearly para-NP-hard if $$j$$ is not in the problem name, but the parameter itself, since $$[1,1]$$-dominating set is the dominating set problem, which is NP-hard.
• The $k$-Clique problem is not solvable in polynomial time. Aug 4, 2023 at 13:03