# Running time analysis of problems with a variable in problem definition

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.

• 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. Aug 2 at 9:57
• If $j$ is allowed to vary, you can also say that the problem is fixed-parameter tractable, with $j$ being the parameter. Aug 2 at 10:14
• 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 Aug 2 at 10:20

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.
• In order to prove that the problem is W-hard for some parameter $P$, in the solution size of the reduced instance am I allowed to have $j$ in some form? Aug 15 at 16:01
• You'd typically say that the problem is W-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$. Aug 16 at 20:46
• But wouldn't the reduction collapse if $j$ is some function of $n$? say $n^{0.2}$ Aug 18 at 3:57
• 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. Aug 18 at 16:55