TransWikia.com

Proving membership in W-hierarchy when problem is not parameterized by its solution size

Theoretical Computer Science Asked by Haden Hooyeon Lee on November 19, 2021

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.

One 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.

Answered by Christian Komusiewicz on November 19, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP