<p>You seem to be studying the <a href="https://en.wikipedia.org/wiki/Parameterized_complexity" rel="noreferrer">parameterized complexity</a> of the problem. This is a branch of Complexity Theory where you add a <em>parameter</em>, which is part of the input but is seen as a separate value.</p>
<p>For example, if one looks at the <span class="math-container">$k$</span>-Clique problem, where <span class="math-container">$k$</span> is a fixed constant, then it is trivially solvable in polynomial time with a <span class="math-container">$O(|V|^k\times|E|)$</span> algorithm. However, in Parameterized Complexity there is a finer notion called <em>fixed-parameter tractable</em>, which states that for an input <span class="math-container">$(x, k)$</span>, where <span class="math-container">$k$</span> is the <em>parameter</em> of the input, the problem can be solved in <span class="math-container">$O(f(k)\times n^c)$</span> time for some constant <span class="math-container">$c$</span>. There is a long-standing conjecture that says the <span class="math-container">$k$</span>-Clique problem, where <span class="math-container">$k$</span> is the parameter, is <strong>not</strong> fixed-parameter tractable. If that were true, it would be in a sense harder than other NP-complete problems such as finding a <a href="https://en.wikipedia.org/wiki/Vertex_cover" rel="noreferrer">vertex cover</a> of size <span class="math-container">$k$</span>, for which there is a known <span class="math-container">$O(2^k\times |G|^c)$</span> algorithm.</p>
<p>To answer your question, I would suggest you say the <span class="math-container">$[1,j]$</span>-domination problem, where <span class="math-container">$j$</span> is the parameter, is <strong>fixed-parameter tractable</strong> for the class <span class="math-container">$C$</span> like @emil-jeřábek said. That way it is clear that your algorithm runs in <span class="math-container">$O(f(j)\times n^c)$</span> time, and that <span class="math-container">$j$</span> does not depend on <span class="math-container">$n$</span>. If you just say that the problem is <em>polynomial when <span class="math-container">$j$</span> is fixed</em>, it would still be true, but it could still mean that your algorithm runs in <span class="math-container">$O(n^j)$</span> time.</p>
<p>As a last comment, if you simply say the algorithm runs in polynomial time for class <span class="math-container">$C$</span>, without saying anything regarding <span class="math-container">$j$</span>, then it could mislead people into thinking that your algorithm runs in <span class="math-container">$O(n^c)$</span> time.</p>

CC BY-SA 4.0
2023-08-15T16:01:53.090Z
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?
Balchandar Reddy
CC BY-SA 4.0
2023-08-16T20:46:01.867Z
You'd typically say that the problem is W[1]-hard under [FPT-reductions](https://en.wikipedia.org/wiki/Parameterized_complexity#:~:text=a%20parameterised%20notion%20of%20reductions%20called%20fpt%2Dreductions) (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$.
alsips-cl
CC BY-SA 4.0
2023-08-18T03:57:09.490Z
But wouldn't the reduction collapse if $j$ is some function of $n$? say $n^{0.2}$
Balchandar Reddy
CC BY-SA 4.0
2023-08-18T16:55:41.860Z
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.
alsips-cl
CC BY-SA 4.0
2023-08-13T23:03:26.487Z
2023-08-13T23:04:35.757Z
2023-08-13T23:04:35.757Z
alsips-cl
<p>I am a research scholar in the field of algorithms and complexity theory. The problem that I am currently working is the <span class="math-container">$[1,j]$</span>-domination problem. Given a graph <span class="math-container">$G = (V, E)$</span>, <span class="math-container">$n = |V|$</span>, the problem asks to compute a minimum dominating set <span class="math-container">$D$</span>, such that all the vertices outside the solution set <span class="math-container">$D$</span> have at most <span class="math-container">$j$</span> vertices in <span class="math-container">$D$</span>. Let's say, I have an algorithm for some particular graph class <span class="math-container">$C$</span> with the running time <span class="math-container">$2^j*poly(n)$</span>. Can I say that the problem is polynomial time solvable for graph class <span class="math-container">$C$</span>? <br> My main question is, should I always consider <span class="math-container">$j$</span> to be a constant, can't it be some function of <span class="math-container">$n$</span> that ruins everything? Please clarify.</p>

CC BY-SA 4.0
2023-08-02T09:57:49.627Z
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.
Laakeri
CC BY-SA 4.0
2023-08-02T10:14:02.733Z
If $j$ is allowed to vary, you can also say that the problem is fixed-parameter tractable, with $j$ being the parameter.
Emil Jeřábek
CC BY-SA 4.0
2023-08-02T10:20:30.190Z
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
Balchandar Reddy
<graph-algorithms><polynomial-time>
Running time analysis of problems with a variable in problem definition
Balchandar Reddy
# Running time analysis of problems with a variable in problem definition

(Asked by: username_0 on 2023-08-02)

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.

**Tags:** graph-algorithms, polynomial-time
> **Comments:**
> **username_1**: 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.  
> **username_2**: If $j$ is allowed to vary, you can also say that the problem is fixed-parameter tractable, with $j$ being the parameter.  
> **username_0**: 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  

---

## 1 answers

### Answer by username_3 on 2023-08-13. Score: 7 | Accepted answer

You seem to be studying the [parameterized complexity](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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?  
> **username_3**: You'd typically say that the problem is W[1]-hard under [FPT-reductions](https://en.wikipedia.org/wiki/Parameterized_complexity#:~:text=a%20parameterised%20notion%20of%20reductions%20called%20fpt%2Dreductions) (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$.  
> **username_0**: But wouldn't the reduction collapse if $j$ is some function of $n$? say $n^{0.2}$  
> **username_3**: 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.  

---

