# The Inapproximability of \(k\)-DominatingSet for Parameterized AC\({}^{0}\) Circuits +
## 3 Introducing Gap to the \(k\)-SetCover Problem
* \(A=\cup_{l\in[m]}A_{i}\) with each \(A_{i}=\{\boldsymbol{a}\ \mid\ \boldsymbol{a}=(a_{1},\ldots,a_{k}),a_{j}\in[h]\text{ for }j\in[k]\}\);
* \(B=\cup_{i\in[k]}B_{i}\) with \(B_{i}=S_{i}\) for \(i\in[k]\);
* \(E=\{\{\boldsymbol{a},b\}\ \mid\ \boldsymbol{a}\in A_{i},b\in B_{j}\text{ and }M_{i,b}= \boldsymbol{a}[j]\text{, for }i\in[m],j\in[k]\}\), that is, for every \(i\in[m],j\in[k]\) and every \(\boldsymbol{a}\in A_{i},b\in B_{j}\), if \(M_{i,b}=\boldsymbol{a}[j]\) then we add an edge between \(\boldsymbol{a}\) and \(b\). We prove that \(T\) is a \((k,n,n\log h,h^{k},h)\)-Gap-Gadget. It is clear that (G1) and (G2) hold for \(T\). For (G3), given any \(b_{1}\in B_{1},\ldots,b_{k}\in B_{k}\), we know that for each \(i\in[m]\), \((M_{i,b_{1}},\ldots,M_{i,b_{k}})\in A_{i}\), which is adjacent to \(b_{1},\ldots,b_{k}\). If \(T\) does not satisfy (G4), then there exists \(X\subseteq B\) with \(|X|\leq h\) such that there is \(\boldsymbol{a}_{1}\in A_{1},\ldots,\boldsymbol{a}_{m}\in A_{m}\) and \(\boldsymbol{a}_{i}\) has at least \(k+1\) neighbors in \(X\) for each \(i\in[m]\). Since \(|X|\leq h\), we know that there is a row \(r\in[m]\) such that \(|\{M_{r,c}\ \mid\ c\in X\}|=X\). For this \(r\), there exist some \(j\in[k]\) such that \(\boldsymbol{a}_{r}\) has at least 2 neighbors \(b_{1}\
eq b_{2}\) in \(B_{j}\). However, \(\{\boldsymbol{a}_{r},b_{1}\}\) and \(\{\boldsymbol{a}_{r},b_{2}\}\in E\) means that \(b_{1}=b_{2}=M_{i,b_{1}}\). This implies \(|\{M_{r,c}\ \mid\ c\in X\}|<X\), which is a contradiction. The \(\mathsf{C}_{k,n,h}\) outputs \(T\) with \(kl^{k}n^{2}\log h\) bits where whether \(\boldsymbol{a}\) and \(b\) are connected is determined by  
\[\mathsf{bit}_{T}\{\boldsymbol{a},b\}= \begin{cases}1&\text{ if }M_{i,b}= \boldsymbol{a}[j]\\ 0&\text{ otherwise}\end{cases} \]  
for every \(\boldsymbol{a}\in A_{i},b\in B_{j}\). Given a set cover instance \(I=(S,U,E)\), we construct the gap gadget \(T=(A,B,E_{T})\) with \(B=S\). To use the gap gadget, we construct a new set cover instance \(I^{\prime}=(S^{\prime},U^{\prime},E^{\prime})\) with \(S^{\prime}=S\) such that for every \(X\subseteq S^{\prime}\) which covers \(U^{\prime}\), there exists \(a_{1}\in A_{1},\ldots,a_{m}\in A_{m}\) witnessing that there is an \(X^{\prime}\subseteq X\) which covers \(U\) and each vertex of which is adjacent to \(a_{i}\) for some \(i\in[m]\). In the following lemma, we use the hypercube set system, which is firstly presented in [PERSON]'s work [12] and is also used in [16; 17; 18]. The set \(X^{Y}=\{f:Y\to X\}\) is considered to be all the functions from \(Y\) to \(X\) with \(|X^{Y}|=|X|^{|Y|}\). **Lemma 3**. : _There is a constant-depth circuit family \((\mathsf{C}_{n,k})_{n,k\in\mathbb{N}}\) which, for each \(k\in\mathbb{N}\), given a set cover instance \(I=(S,U,E)\) where \(S=S_{1}\cup\cdots\cup S_{k}\) and \(|S_{i}|=n\) for \(i\in[k]\) and a \((k,n,m,\ell,h)\)-Gap-Gadget constructed with \(S\) as Lemma 2 describes, outputs a set cover instance \(I^{\prime}=(S^{\prime},U^{\prime},E)\) with \(S^{\prime}=S\) and \(|U^{\prime}|=m|U|^{\ell}\) such that_  
* _If there exists_ \(s_{1}\in S_{1},\ldots,s_{k}\in S_{k}\) _which could cover_ \(U\)_, then the set cover number of_ \(I^{\prime}\) _is at most_ \(k\)_;_
* _If the set cover number of_ \(I\) _is larger than_ \(k\)_, then the set cover number of_ \(I^{\prime}\) _is greater than_ \(h\)_._  
_Furthermore, the circuit \(\mathsf{C}_{n,k}\) has size at most \(knm\ell|U|^{\ell}\) and could output whether \(s\) and \(f\) are connected with at most \((\ell+1)\) gates._  
**Proof. ** Let \(T=(A=\cup_{i\in[m]}A_{i},B,E_{T})\) be the \((k,n,m,\ell,h)\)-Gap-Gadget with \(B_{i}=S_{i}\) for \(i\in[k]\). \(I^{\prime}=(S^{\prime},U^{\prime},E^{\prime})\) is defined as follows. * \(S^{\prime}=S\);
* \(U^{\prime}=\cup_{i\in[m]}U^{A_{i}}\);
* For every \(s\in S^{\prime}\) and \(f\in U^{A_{i}}\) for each \(i\in[m]\), \(\{s,f\}\in E^{\prime}\) if there is an \(a\in A_{i}\) such that \(\{s,f(a)\}\in E\) and \(\{a,s\}\in E_{T}\).