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.
$\begingroup$
$\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$– LaakeriAug 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$– Emil JeřábekAug 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$– Balchandar ReddyAug 2 at 10:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
$\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$ 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$ Aug 18 at 16:55