3
$\begingroup$

I am a research scholar in the field of algorithms and complexity theory. The problem that I am currently working is the $[1,j]$-domination problem. Given a graph $G = (V, E)$, $n = |V|$, the problem asks to compute a minimum dominating set $D$, such that all the vertices outside the solution set $D$ have at most $j$ vertices in $D$. Let's say, I have an algorithm for some particular graph class $C$ with the running time $2^j*poly(n)$. Can I say that the problem is polynomial time solvable for graph class $C$?
My main question is, should I always consider $j$ to be a constant, can't it be some function of $n$ that ruins everything? Please clarify.

$\endgroup$
3
  • 1
    $\begingroup$ The usual convention is that if the variable is in the name of the problem, then it can be considered to be a constant. So if the problem name is "[1,j]-domination", then $j$ is considered to be a constant. $\endgroup$
    – Laakeri
    Aug 2 at 9:57
  • $\begingroup$ If $j$ is allowed to vary, you can also say that the problem is fixed-parameter tractable, with $j$ being the parameter. $\endgroup$ Aug 2 at 10:14
  • $\begingroup$ So, do you mean I could safely say that the problem is polynomial-time solvable for graph class $C$ without worrying about what $j$ can be (as $j$ is assumed to be a constant)? @Laakeri $\endgroup$ Aug 2 at 10:20

1 Answer 1

7
$\begingroup$

You seem to be studying the parameterized complexity of the problem. This is a branch of Complexity Theory where you add a parameter, which is part of the input but is seen as a separate value.

For example, if one looks at the $k$-Clique problem, where $k$ is a fixed constant, then it is trivially solvable in polynomial time with a $O(|V|^k\times|E|)$ algorithm. However, in Parameterized Complexity there is a finer notion called fixed-parameter tractable, which states that for an input $(x, k)$, where $k$ is the parameter of the input, the problem can be solved in $O(f(k)\times n^c)$ time for some constant $c$. There is a long-standing conjecture that says the $k$-Clique problem, where $k$ is the parameter, is not fixed-parameter tractable. If that were true, it would be in a sense harder than other NP-complete problems such as finding a vertex cover of size $k$, for which there is a known $O(2^k\times |G|^c)$ algorithm.

To answer your question, I would suggest you say the $[1,j]$-domination problem, where $j$ is the parameter, is fixed-parameter tractable for the class $C$ like @emil-jeřábek said. That way it is clear that your algorithm runs in $O(f(j)\times n^c)$ time, and that $j$ does not depend on $n$. If you just say that the problem is polynomial when $j$ is fixed, it would still be true, but it could still mean that your algorithm runs in $O(n^j)$ time.

As a last comment, if you simply say the algorithm runs in polynomial time for class $C$, without saying anything regarding $j$, then it could mislead people into thinking that your algorithm runs in $O(n^c)$ time.

$\endgroup$
4
  • $\begingroup$ In order to prove that the problem is W[1]-hard for some parameter $P$, in the solution size of the reduced instance am I allowed to have $j$ in some form? $\endgroup$ Aug 15 at 16:01
  • $\begingroup$ You'd typically say that the problem is W[1]-hard under FPT-reductions (or simply "under parameterized reductions"), which is a finer version of Karp reductions. In short, yes you can have $j$ in the size of the new instance, but not as an exponent of $n$. $\endgroup$
    – alsips-cl
    Aug 16 at 20:46
  • $\begingroup$ But wouldn't the reduction collapse if $j$ is some function of $n$? say $n^{0.2}$ $\endgroup$ Aug 18 at 3:57
  • $\begingroup$ It would, so don't do that. When you express a complexity bound as a function of different parameters they are considered independent. Like, a graph algorithm that runs in $O(|V|^2\times|E|)$ means that the runtime grows quadratically if you increase the number of vertices while keeping the number of edges constant. $\endgroup$
    – alsips-cl
    Aug 18 at 16:55

Your Answer

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

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