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.
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Aug 7, 2020 at 9:04
-
$\begingroup$ Indeed after so many years, somehow not many problems have been proved in this category .. Even i'll keep searching and post here in case i find something .. This is the first result on W[3] that i came across .. So thank you! $\endgroup$ Commented Aug 7, 2020 at 14:23
-
$\begingroup$ @VenugopalK You're welcome. Note that you can also choose to accept an answer if it has been useful to you. $\endgroup$– Discrete lizard ♦Commented Aug 7, 2020 at 14:45