Role of a variable in problem definition in time complexity

Question

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)$, with $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$ neighbours in $D$.

Let's say I have an algorithm for some particular graph class $C$ with the running time $2^j \cdot \text{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?

Answer 1

Can I say that the problem is polynomial time solvable for graph class $C$?

Yes, you can say that if you want to.

Should I always consider j to be a constant, can't it be some function of n that ruins everything?

This is something we usually state explicitly, however, if you call the problem the $[1, 5]$-Dominating Set, then, obviously $5$ is a constant. If you say $[1,j]$-Dominating Set, you should clarify whether $j$ is considered to be a constant.

Typically, I would write $[1,j]$-Dominating Set is polynomial time solvable when $j$ is a fixed integer. The problem is solvable in time $2^j n^{O(1)}$ whenever $j$ is considered as part of the input.

If $j$ is considered a parameter, then in parameterized complexity the problem would be fixed-parameter tractable.

---

In other words: Is $j$ part of the input to your algorithm? Or is your algorithm "hardcoded" with a fixed $j$ somewhere?

Answer 2

Let the running time of an algorithm be $T(m,n)=a^mp(n)$. If $m$ is a growing function of $n$, then

$$T'(n)=T(m(n),n)=2^{m(n)}f(n)$$ which can very well be exponential. To keep a polynomial behavior, you need

$$m(n)=O(\log(q(n)))=O(\log(n)).$$