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?
-
$\begingroup$ Does this answer your question? Role of a variable in problem definition in time complexity $\endgroup$– user16034Commented Aug 4, 2023 at 6:49
-
$\begingroup$ 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 $\endgroup$– Balchandar ReddyCommented Aug 4, 2023 at 9:51
-
$\begingroup$ As long as it is mentioned in the problem name, it can be considered as a constant. $\endgroup$– Narek BojikianCommented Aug 4, 2023 at 11:46
-
$\begingroup$ @NarekBojikian That's not correct. You need to take into account that they are looking for parameterized reductions. $\endgroup$– John KemenyCommented Aug 4, 2023 at 12:50
-
$\begingroup$ 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) $\endgroup$– Narek BojikianCommented Aug 4, 2023 at 12:56
1 Answer
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.
-
$\begingroup$ The $k$-Clique problem is not solvable in polynomial time. $\endgroup$ Commented Aug 4, 2023 at 13:03