4
$\begingroup$

I have a problem $\mathsf{A}$ and I would like to analyze its (parameterized) computational complexity.

I found a parameterized reduction from the complement of the independent set ($\mathsf{coIS}$) problem (i.e. given a graph $G$ and an integer $k$, is there no independent set of size $k$ in G?), such that there is a parameter $\kappa$ to my new problem $\mathsf{A}$ that only increases by a constant in regards to $k$.

Formally, I have found a reduction function $R$, that takes as input an instance $(G, k)$ of $\mathsf{coIS}$, where $G$ is an arbitrary undirected graph and $k \in \mathbf{N}$ is some integer, and outputs an instance $(I, \kappa)$ of problem $\mathsf{A}$, such that:

  1. $(G, k) \in \mathsf{coIS} \Leftrightarrow (I, \kappa) \in \mathsf{A}$ (alternatively: $(G, k) \not\in \mathsf{IS} \Leftrightarrow (I, \kappa) \in \mathsf{A}$).
  2. $R$ runs in $f(k) \cdot |G|^{\mathcal{O}(1)}$ time, where $f$ is some computable function (in our case, $f$ is polynomial).
  3. $\kappa \leq h(k)$, where $h$ is some computable function.

From this, I infer that problem $\mathsf{A}$ is coNP-hard. However, I would also like to make a statement about the parameterized complexity of problem $\mathsf{A}$. My intuition tells me that problem $\mathsf{A}$ is $coW[1]$-hard when parameterized by $\kappa$.

However, I have not been able to find any reference to the class $coW[1]$ in the literature or in any previously asked question. Given that my understanding of the class $W[1]$ and the $W$-hierarchy is somewhat primitive, I don't know if the notion of $coW[1]$ makes any sense. I could well imagine that $W[1] = coW[1]$ holds, but I don't know how one would prove such a statement.

$\endgroup$

1 Answer 1

3
$\begingroup$

The paper The Parameterized Complexity of Local Consistency by Gaspers and Szeider discusses coW[1]- and coW[2]-complete problems. This is maybe a starting point.

$\endgroup$

Your Answer

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

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