1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Does this answer your question? Role of a variable in problem definition in time complexity $\endgroup$
    – user16034
    Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Aug 4, 2023 at 12:56

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The $k$-Clique problem is not solvable in polynomial time. $\endgroup$ Commented Aug 4, 2023 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.