Question

We are currently working on a variant of domination parameter and we have shown that it is in W[3] with regard to parameterized complexity. To show it is W[3]-complete, we must show the problem is W[3] hard i.e, reduce an already known W[3] hard problem to ours. But unlike W[1] and W[2], where many famous problems are proved those classes, surprisingly we have not come across a single problem that is W[3] hard and not even in just W[3]. Of course there is the general W[t] case which we can go for, but any result for W[3] in particular would help a lot.

Was it helpful?

Solution

There are a few examples in the answer to Natural complete problems in higher levels of the W-hierarchy. In particular, the W[3]-complete problem $p$-HYPERGRAPH-(NON)-DOMINATING-SET may be useful for your proof.

Given that the linked question is now almost 6 years old, you'd perhaps expect some more examples to pop up by now. However, I couldn't find anything concrete in a quick literature search. The closest thing I could find was Separating sets of strings by finding matching patterns is almost always hard (2017) by Lancia et al., where they conjecture that the problem they call PATTERN IDENTIFICATION is W[3]-complete for a particular parameter, but this conjecture is probably not very useful for your proof. I do note that I'm not an expert in this field, so there may be some more recent results out there I simply wasn't able to find.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top