# The Inapproximability of \(k\)-DominatingSet for Parameterized AC\({}^{0}\) Circuits +
## 4 Inapproximability of \(k\)-DominatingSet
### The Unconditional Inapproximability of \(k\)-DominatingSet
There is a \((C_{n,k})_{n,k\in\mathbb{N}}\) circuit family which, given a \(k\)-Clique instance \(G\) with \(|V_{G}|=n\), could output a set cover instance \(I=(S,U,E)\) with \(|U|\leq n^{5}\) and \(S\leq\binom{k}{2}\binom{n}{2}\) such that  
* If \(G\) contains a \(k\)-clique, then the set cover number of \(I\) is at most \(\binom{k}{2}\);
* If \(G\) contains no \(k\)-clique, then the set cover number of \(I\) is greater than \(\left(\frac{\log n}{\log\log n}\right)^{1/\binom{k}{2}}\). _Furthermore, \(\mathsf{C}_{n,k}\) has constant depth and size at most \(n^{7}\log n\)._  
By Lemma 4, we can construct a \(\binom{k}{2}\)-SetCover instance \(I=(S,U,E)\) with \(|S|\leq\binom{k}{2}(\binom{n}{2})\) and \(|U|\leq k^{3}\log n\), using a constant-depth circuit of size at most \(k^{5}n^{2}\log n\). Let \(m=\binom{n}{2}\). By Lemma 2, we can construct a \(\binom{(k)}{2},m,m\log h,h^{(\frac{k}{2})},h\)-Gap-Gadget \(T\) with \(h=\left(\frac{\log m}{\log\log m}\right)^{1/\binom{k}{2}}\) given \(S\), using a constant-depth circuit of size at most \(O(n^{2}\log^{2}n)\). By Lemma 3, we could have a constant-depth circuit of size at most \(n^{7}\log n\) which computes a set cover instance \(I^{\prime}=(S^{\prime},U^{\prime},E^{\prime})\) with \(S^{\prime}=S\), \(|U^{\prime}|\leq m\log h(k^{3}\log n)^{h^{(\frac{k}{2})}}\) such that  
* If \(G\) contains a \(k\)-clique, then the set cover number of \(I\) is at most \(\binom{k}{2}\);
* If \(G\) contains no \(k\)-clique, then the set cover number of \(I\) is greater than \(\left(\frac{\log m}{\log\log m}\right)^{1/\binom{k}{2}}\geq\left(\frac{\log n }{\log\log n}\right)^{1/\binom{k}{2}}\). Here, since \((k^{3}\log n)^{\frac{\log m}{\log\log m}}\leq(k^{3}\log n)^{\frac{2\log n}{ \log\log n}}\leq(k^{\frac{\log n}{\log\log n}})^{6}\cdot n^{2}\leq n^{\frac{4k }{\log\log n}}\cdot n^{2}\leq n^{2+o(1)}\), we can conclude that \(|U^{\prime}|\leq m\log h(k^{3}\log n)^{h^{(\frac{k}{2})}}\leq n^{2}\log n\cdot n ^{2+o(1)}\leq n^{4+o(1)}<n^{5}\). **Theorem 3**. : _Given a set cover instance \(I=(S,U,E)\) with \(n=|S|+|U|\), for \(k>28\), any constant-depth circuit of size \(O(n^{\frac{\sqrt{k}}{2}})\) cannot distinguish between_  
* _The set cover number of_ \(I\) _is at most_ \(k\)_, or_
* _The set cover number of_ \(I\) _is greater than_ \(\left(\frac{\log n}{\log\log n}\right)^{1/\binom{k}{2}}\)_._  
[PERSON] showed that for every \(k\in\mathbb{N}\), the \(k\)-Clique problem on \(n\)-vertex graphs requires constant-depth circuits of size \(\omega(n^{\frac{k}{4}})\)[25]. Now if there is a constant-depth circuit \(\mathsf{C}_{n,k}\) of size \(O(n^{\frac{\sqrt{k}}{20}})\) that could distinguish between the set cover number of \(I\) where \(|V_{I}|=n\) is at most \(k\) or greater than \(\left(\frac{\log n}{\log\log n}\right)^{1/\binom{k}{2}}\), then by Lemma 5, given \(k\in\mathbb{N}\) and a graph \(G\) with \(|V_{G}|=n\), we can construct a set cover instance \(I\) with vertex number at most \(2n^{5}\) satisfying that if \(G\) has a \(k\)-clique then the set cover number of \(I\) is at most \(\binom{k}{2}\) and otherwise it is greater than \(\left(\frac{\log n}{\log\log n}\right)^{1/\binom{k}{2}}\)--we could use \(\mathsf{C}_{2n^{5},\binom{k}{2}}\) to decide whether the set cover number of \(I\) is either \(\leq\binom{k}{2}\) or \(>\left(\frac{\log n}{\log\log n}\right)^{1/\binom{k}{2}}\). The circuits are of size \(O((n^{5})^{\sqrt{\binom{k}{2}}/20})+O(n^{7}\log n)=O(n^{\frac{k}{4}})\) when \(k>28\), which contradicts the result shown by [PERSON] [25]. Note that Theorem 3 implies Theorem 1 since for every set cover instance \(I=(S,U,E)\) we can construct a dominating set instance \(I^{\prime}=(S\cup U,E\cup\left\{\left\{u,v\right\}\mid u,v\in S\right\})\) simply by adding edges to \(S\) so that it becomes a clique. Then the dominating number of \(I^{\prime}\) is the same as the set cover number of \(I\).