patternMinor
Is there such a thing as $coW[1]$-hardness?
Viewed 0 times
suchcowhardnesstherething
Problem
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:
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.
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:
- $(G, k) \in \mathsf{coIS} \Leftrightarrow (I, \kappa) \in \mathsf{A}$ (alternatively: $(G, k) \not\in \mathsf{IS} \Leftrightarrow (I, \kappa) \in \mathsf{A}$).
- $R$ runs in $f(k) \cdot |G|^{\mathcal{O}(1)}$ time, where $f$ is some computable function (in our case, $f$ is polynomial).
- $\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.
Solution
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.
Context
StackExchange Computer Science Q#159918, answer score: 3
Revisions (0)
No revisions yet.