<p>The answer to your updated Question (1) &quot;When a problem is parameterized by something other than the size of a solution (and as a result, the size of a solution is still unbounded in terms of the parameter), then [is it] W[t]-hard for all t, at least?&quot; is no. Independent Set for example is FPT with respect to the treewidth <span class="math-container">$\omega$</span> of the input graph. The solution size <span class="math-container">$k$</span> (essentially the size of a largest independent set of the input graph) can be much larger than <span class="math-container">$\omega$</span>.</p>
<p>In general, a parameter can be anything that is related to the input instance. The <em>standard</em> parameter solution size is just one of many different ways to parameterize a problem.</p>

CC BY-SA 4.0
2020-07-28T03:35:57.540Z
I thought in full generality, the parameter can be *anything*, not necessarily related to the instance? it's just that in practice the only interesting parameterized problems are those where there is some relation
Joshua Grochow
CC BY-SA 4.0
2020-07-28T07:11:40.483Z
@JoshuaGrochow Yes you are absolutely right. There are several definitions of parameterized problems or parameterizations. I personally like the definition where the parameter is defined via a polynomial-time computable function $\kappa: \Sigma^* \to \mathbb{N}$. For this definition, the parameter is related to the input instance but of course the function can be just a constant. For the classic definition where the parameter is simply a number, the meaning of the parameter is usually encoded in the problem definition. Should I add (a short version of) this discussion to the answer?
Christian Komusiewicz
CC BY-SA 4.0
2020-07-28T21:51:52.453Z
Either way is fine, I just wanted to check my understanding. Thanks!
Joshua Grochow
CC BY-SA 4.0
2020-07-25T19:55:40.553Z
2020-07-25T19:55:40.553Z
Christian Komusiewicz
<p>I'm curious about the following general problem:</p>
<p>Suppose that we have a parameterized problem whose input is <span class="math-container">$x$</span> and parameter is <span class="math-container">$k$</span> (which is NOT the size of a solution but something about the input), and we know that its solution size can be as big as <span class="math-container">$|x|$</span> in general.</p>
<p>One example is the Independent Set Problem parameterized by the max-degree of a vertex, where we ask whether there exists an independent set of size at least <span class="math-container">$s$</span> (which is NOT the parameter) given a graph of <span class="math-container">$n$</span> vertices with max-degree <span class="math-container">$d$</span> (which is the parameter).</p>
<p>(Compare this with the Clique problem with bounded degree, which is in FPT -- here, the size of a solution (clique) is also bounded because of the bounded degree, so it's different.)</p>
<p>(1) First of all, is this even a fair parameterized problem, when the size of a solution is only polynomially bounded by the size of an input (because <span class="math-container">$s$</span> can be as large as <span class="math-container">$n$</span>)?</p>
<p>The reason for this first question is mainly because I can't imagine how this problem can be reduced to the weft-t weighted circuit satisfiability problem to show that it belongs to W[t] (for t &gt;= 1), in particular, if it does belong. Specifically, a solution (= a large independent set) would have to contain <span class="math-container">$s$</span> vertices, but we can only set <span class="math-container">$f(d)$</span> input nodes to true in a hypothetical WCSAT instance we create (since <span class="math-container">$d$</span> is the only parameter being considered).</p>
<p>This makes me think that perhaps the problem I wrote above is ill-defined in the first place (or, maybe it trivially implies that it can't belong to W[t] for any fix t, but this is what I am confused about). As a follow-up if the above problem is well-defined and it actually belongs to W[t] for some constant t, I'd love to know how one can show that.</p>
<p>Update: After my initial post, I realized that this is (probably) para-NP-hard since the independent set problem is already NP-hard when <span class="math-container">$d = 3$</span>, and so is the vertex coloring problem. What I meant to ask was (not specifically about the independent set problem I wrote) whether this is in general true: When a problem is parameterized by something other than the size of a solution (and as a result, the size of a solution is still unbounded in terms of the parameter), then does it imply that the parameterized problem is W[t]-hard for all t, at least?</p>
<p>(2) My next question is (if this question makes sense):
When we try to show that a problem that is not parameterized by the size of a solution AND its solution size (under the said parameterization) is still only polynomial in input size, what are some known techniques for doing this? Are there any known problems (assuming that my question in the previous paragraph was &quot;NO, it's not always implied&quot;)?</p>
<p>I'd love to see relevant examples and papers, if anyone can recommend.
I've searched a few references, but I couldn't quite find an answer to my questions.</p>

CC BY-SA 4.0
2020-07-25T19:56:39.657Z
Could you rephrase Question (2)? It is not clear to me what you are asking.
Christian Komusiewicz
CC BY-SA 4.0
2020-07-27T18:16:43.910Z
Thanks for answering the first question!
For (2), I'm looking for any known reductions of the following:
Given a parameterized problem X (whose parameter is not the size of a solution and the size of a solution can still be quite large -- just like the independent set parameterized by tree width  you mentioned) showing X is W[t]-complete for some fixed t>=1 (e.g., W[1]-complete, W[2]-complete, but not in FPT). 
So I'm curious how one can show that X is in W[1] or W[2], e.g., when the size of a solution can still be "n" yet we can only choose "k" input gates  as it seems impossible.
Haden Hooyeon Lee
CC BY-SA 4.0
2020-07-27T21:55:53.153Z
I find the second question interesting. Following the general guidelines of Stack Overflow network, I would suggest asking it as a new questions, making it easier to find for people asking similar questions (and also easier to get an answer). Most results do not show completeness in the W-hierarchy. Usually a paper only shows hardness, since this is enough evidence for ruling out an FPT algorithm. Indeed, it could be the case that for many known problems, even though they are hard for W[i], they are not complete, since they could require weft strictly greater than i.
Vinicius dos Santos
CC BY-SA 4.0
2020-07-28T22:39:36.497Z
^ Thanks for the suggestion, and I created a new question. 
https://cstheory.stackexchange.com/questions/47294/reducing-parameterized-problems-whose-solution-size-can-be-large-to-wi-comp
Haden Hooyeon Lee
<parameterized-complexity><fixed-parameter-tractable>
Proving membership in W-hierarchy when problem is not parameterized by its solution size
Haden Hooyeon Lee
# Proving membership in W-hierarchy when problem is not parameterized by its solution size

(Asked by: username_0 on 2020-07-22)

I'm curious about the following general problem:

Suppose that we have a parameterized problem whose input is $x$ and parameter is $k$ (which is NOT the size of a solution but something about the input), and we know that its solution size can be as big as $|x|$ in general.

One example is the Independent Set Problem parameterized by the max-degree of a vertex, where we ask whether there exists an independent set of size at least $s$ (which is NOT the parameter) given a graph of $n$ vertices with max-degree $d$ (which is the parameter).

(Compare this with the Clique problem with bounded degree, which is in FPT -- here, the size of a solution (clique) is also bounded because of the bounded degree, so it's different.)

(1) First of all, is this even a fair parameterized problem, when the size of a solution is only polynomially bounded by the size of an input (because $s$ can be as large as $n$)?

The reason for this first question is mainly because I can't imagine how this problem can be reduced to the weft-t weighted circuit satisfiability problem to show that it belongs to W[t] (for t >= 1), in particular, if it does belong. Specifically, a solution (= a large independent set) would have to contain $s$ vertices, but we can only set $f(d)$ input nodes to true in a hypothetical WCSAT instance we create (since $d$ is the only parameter being considered).

This makes me think that perhaps the problem I wrote above is ill-defined in the first place (or, maybe it trivially implies that it can't belong to W[t] for any fix t, but this is what I am confused about). As a follow-up if the above problem is well-defined and it actually belongs to W[t] for some constant t, I'd love to know how one can show that.

Update: After my initial post, I realized that this is (probably) para-NP-hard since the independent set problem is already NP-hard when $d = 3$, and so is the vertex coloring problem. What I meant to ask was (not specifically about the independent set problem I wrote) whether this is in general true: When a problem is parameterized by something other than the size of a solution (and as a result, the size of a solution is still unbounded in terms of the parameter), then does it imply that the parameterized problem is W[t]-hard for all t, at least?

(2) My next question is (if this question makes sense):
When we try to show that a problem that is not parameterized by the size of a solution AND its solution size (under the said parameterization) is still only polynomial in input size, what are some known techniques for doing this? Are there any known problems (assuming that my question in the previous paragraph was "NO, it's not always implied")?

I'd love to see relevant examples and papers, if anyone can recommend.
I've searched a few references, but I couldn't quite find an answer to my questions.

**Tags:** parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: Could you rephrase Question (2)? It is not clear to me what you are asking.  
> **username_0**: Thanks for answering the first question! For (2), I'm looking for any known reductions of the following: Given a parameterized problem X (whose parameter is not the size of a solution and the size of a solution can still be quite large -- just like the independent set parameterized by tree width  you mentioned) showing X is W[t]-complete for some fixed t>=1 (e.g., W[1]-complete, W[2]-complete, but not in FPT).  So I'm curious how one can show that X is in W[1] or W[2], e.g., when the size of a solution can still be "n" yet we can only choose "k" input gates  as it seems impossible.  
> **username_2**: I find the second question interesting. Following the general guidelines of Stack Overflow network, I would suggest asking it as a new questions, making it easier to find for people asking similar questions (and also easier to get an answer). Most results do not show completeness in the W-hierarchy. Usually a paper only shows hardness, since this is enough evidence for ruling out an FPT algorithm. Indeed, it could be the case that for many known problems, even though they are hard for W[i], they are not complete, since they could require weft strictly greater than i.  
> **username_0**: ^ Thanks for the suggestion, and I created a new question.  https://cstheory.stackexchange.com/questions/47294/reducing-parameterized-problems-whose-solution-size-can-be-large-to-wi-comp  

---

## 1 answers

### Answer by username_1 on 2020-07-25. Score: 5 | Accepted answer

The answer to your updated Question (1) "When a problem is parameterized by something other than the size of a solution (and as a result, the size of a solution is still unbounded in terms of the parameter), then [is it] W[t]-hard for all t, at least?" is no. Independent Set for example is FPT with respect to the treewidth $\omega$ of the input graph. The solution size $k$ (essentially the size of a largest independent set of the input graph) can be much larger than $\omega$.

In general, a parameter can be anything that is related to the input instance. The *standard* parameter solution size is just one of many different ways to parameterize a problem.

> **Comments:**
> **username_3**: I thought in full generality, the parameter can be *anything*, not necessarily related to the instance? it's just that in practice the only interesting parameterized problems are those where there is some relation  
> **username_1**: @JoshuaGrochow Yes you are absolutely right. There are several definitions of parameterized problems or parameterizations. I personally like the definition where the parameter is defined via a polynomial-time computable function $\kappa: \Sigma^* \to \mathbb{N}$. For this definition, the parameter is related to the input instance but of course the function can be just a constant. For the classic definition where the parameter is simply a number, the meaning of the parameter is usually encoded in the problem definition. Should I add (a short version of) this discussion to the answer?  
> **username_3**: Either way is fine, I just wanted to check my understanding. Thanks!  

---

