# The Inapproximability of \(k\)-DominatingSet for Parameterized AC\({}^{0}\) Circuits +
## 1 Introduction
### Our Work  
In this paper, we show that for any computable function \(f\), the \(f(k)\)-FPT-approximation of the \(k\)-DomSet problem is not in \(\mathsf{para-AC}^{\mathsf{0}}\). Furthermore, under the hypothesis that constant-depth circuits of size \(2^{o(n)}\) could not compute 3-CNF-SAT (we call it \(\mathsf{AC}^{\mathsf{0}}\)-\(ETH\), the constant-depth version of ETH--the exponential time hypothesis), there is no computable function \(f\) such that the \(f(k)\)-approximation of \(k\)-DomSet could be computed by constant-depth circuits of size \(n^{o(k)}\). Theorems 1 and 2 are direct consequences of Theorems 3 and 4, respectively. **Theorem 1**. : _Given a graph \(G\) with \(n\) vertices, there is no constant-depth circuits of size \(f(k)n^{o(\sqrt{k})}\) for any computable function \(f\) which distinguish between:_  
* _The size of the minimum dominating set is at most_ \(k\)_,_
* _The size of the minimum dominating set is greater than_ \(\left(\frac{\log n}{\log\log n}\right)^{1/\binom{k}{2}}\)_._  
Note that this theorem implies the nonexistence of \(\mathsf{para-AC}^{\mathsf{0}}\) circuits which \(f(k)\)-approximates the \(k\)-DomSet problem for any computable function \(f\). This is because if there is an \(f(k)\)-approximation \(\mathsf{para-AC}^{\mathsf{0}}\) circuit \(\mathsf{C}_{n,k}\) whose size is \(g(k)\mathrm{poly}(n)\), we can construct a constant-depth \(\mathsf{para-AC}^{\mathsf{0}}\) circuit \(\mathsf{C}^{\prime}_{n,k}\) to distinguish the size of the minimum dominating set is at most \(k\) or greater than \(\left(\frac{\log n}{\log\log n}\right)^{1/\binom{k}{2}}\) as follows. Compare \(f(k)\) and \(\left(\frac{\log n}{\log\log n}\right)^{1/\binom{k}{2}}\) -- if \(f(k)\) is smaller, we let \(C^{\prime}_{n,k}\) be \(C_{n,k}\); otherwise, since \(f(k)\geq\left(\frac{\log n}{\log\log n}\right)^{1/\binom{k}{2}}\), we let \(C^{\prime}_{n,k}\) be the circuit which, using brute force, computes the size of a minimum dominating set with the depth-3 circuit of size \(O(n^{k+1})\). Since \(f(k)\geq\left(\frac{\log n}{\log\log n}\right)^{1/\binom{k}{2}}\), we have \(f(k)^{k^{3}}\geq\left(\frac{\log n}{\log\log n}\right)^{2k}\); by simple calculations we know that \(k\cdot\log^{2k-1}n\geq(k+1)(\log\log n)^{2k}\) for \(k\geq 2,n\geq 2\), which implies \(k\cdot\left(\frac{\log n}{\log\log n}\right)^{2k}\geq(k+1)\cdot\log n\), that is, \(2^{k\cdot\left(\frac{\log n}{\log\log n}\right)^{2k}}\geq n^{k+1}\). Thus, we know \(2^{kf(k)^{k^{3}}}\geq n^{k+1}\), which means the circuit is still a para-AC\({}^{0}\) circuit. **Hypothesis 1** (AC\({}^{0}\)-ETH, the constant-depth version of ETH). : _There exists \(\delta>0\) such that no constant-depth circuits of size \(2^{\delta n}\) can decide whether the \(3\)-CNF-SAT instance \(\varphi\) is satisfiable, where \(n\) is the number of variables of \(\varphi\)._  
**Theorem 2**. : _Assuming AC\({}^{0}\)-ETH, given a graph \(G\) with \(n\) vertices, there is no constant-depth circuits of size \(f(k)n^{o(k)}\) for any computable function \(f\) which distinguish between:_  
* _The size of the minimum dominating set of_ \(G\) _is at most_ \(k\)_,_
* _The size of the minimum dominating set of_ \(G\) _is greater than_ \(\left(\frac{\log n}{3\log\log n}\right)^{1/k}\)_._  
Though AC\({}^{0}\)-ETH seems much weaker than ETH (ETH implies the nonexistence of uniform circuits of size \(2^{\delta n}\) and any depth which could compute the \(3\)-CNF-SAT problem), we show that the hypothesis is hard to settle by proving it implies NP \(\
ot\subseteq\) NC\({}^{1}\), which, believed to be true, remains open for decades. Moreover, it is still unknown whether the weaker version, NP \(\
ot\subseteq\) ACC \(\circ\) THR, holds or not. Since our hard set cover instances can be easily reduced to the instances of the total dominating set problem, the connected dominating set problem and the independent dominating set problem, we can apply our inapproximability results to these variants of the dominating set problem.