2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Could you rephrase Question (2)? It is not clear to me what you are asking. $\endgroup$
    – Christian Komusiewicz
    Jul 25, 2020 at 19:56
  • $\begingroup$ 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. $\endgroup$
    – Haden Hooyeon Lee
    Jul 27, 2020 at 18:16
  • 2
    $\begingroup$ 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. $\endgroup$
    – Vinicius dos Santos
    Jul 27, 2020 at 21:55
  • $\begingroup$ ^ Thanks for the suggestion, and I created a new question. cstheory.stackexchange.com/questions/47294/… $\endgroup$
    – Haden Hooyeon Lee
    Jul 28, 2020 at 22:39

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Joshua Grochow
    Jul 28, 2020 at 3:35
  • 1
    $\begingroup$ @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? $\endgroup$
    – Christian Komusiewicz
    Jul 28, 2020 at 7:11
  • $\begingroup$ Either way is fine, I just wanted to check my understanding. Thanks! $\endgroup$
    – Joshua Grochow
    Jul 28, 2020 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.