# The Inapproximability of \(k\)-DominatingSet for Parameterized AC\({}^{0}\) Circuits +
## 4 Inapproximability of \(k\)-DominatingSet
### The Unconditional Inapproximability of \(k\)-DominatingSet  
Now we give the circuits which reduce \(k\)-Clique instances to \(\binom{k}{2}\)-SetCover instances, and introduce gaps to them. Finally we use [PERSON]'s result (25), i.e., the unconditional lower bounds of the sizeof constant-depth circuits determining the \(k\)-Clique problem, to show the inapproximability of the \(k\)-DomSet problem. There is a \((C_{n,k})_{n,k\in\mathbb{N}}\) circuit family which, given a \(k\)-Clique instance \(G\) with \(|V_{G}|=n\), outputs a set cover instance \(I=(S,U,E)\) with \(|U|\leq k^{3}\log n\) and \(S\leq\binom{k}{2}\binom{n}{2}\) such that \(G\) contains a \(k\)-clique if and only if the set cover number of \(I\) is at most \(\binom{k}{2}\). Furthermore, \(C_{n,k}\) has constant depth and size at most \(k^{5}n^{2}\log n\). Firstly, we construct \(G^{\prime}=(V_{1}\cup\cdots\cup V_{k},E^{\prime})\), a \(k\)-colored version of \(G\) as follows. Let each \(V^{(i)}\) be a copy of \(V\) and for every \(v\in V_{G}\), we call the corresponding vertex in \(V^{(i)}\) by \(v^{(i)}\); let \(E^{\prime}=\cup_{1\leq i<j\leq k}E_{i,j}\) with \(E_{i,j}=\{\{u^{(i)},v^{(j)}\}\mid\{u,v\}\in E_{G}\}\). Note that each \(V^{(i)}\) is an independent set for \(i\in[k]\) and \(G^{\prime}\) contains a \(k\)-clique if and only if \(G\) contains a \(k\)-clique. Now we construct the the set cover instance \(I=(S,U,E)\) according to \(G^{\prime}\) in the following way. Given \(v\in G^{\prime}\), we denote by \(\mathbf{b}(v)\) the bit representation of \(v\). Note that when \(i\) is fixed, every vertex in \(V_{i}\) could be determined using \(\log n\) bits. * \(S=E^{\prime}=\cup_{1\leq i<j\leq k}E_{i,j}\);
* \(U=\cup_{i\in[k]}U_{i}\) with \(U_{i}=\{(f^{(i)},I)\mid f^{(i)}:\{0,1\}\to[k]\setminus\{i\},l\in[\log n]\}\);
* For every \(i\in[k]\), we connect every \((f^{(i)},l)\in U_{i}\) to each \(\{v_{i},v_{j}\}\in S\), with \(v_{i}\in V_{i},v_{j}\in V_{j}\), such that \(f^{(i)}(\mathbf{b}(v_{i})[l])=j\). Suppose that there is a \(k\)-clique in \(G^{\prime}\) with vertices \(u_{1}\in V_{1},\ldots,u_{k}\in V_{k}\). We claim that \(\{\{u_{i},u_{j}\}\mid 1\leq i<j\leq k\}\) covers \(U\). This is because for any \((f^{(i)},l)\in U_{i}\), we have \(f^{(i)}(\mathbf{b}(u_{i})[l])\in[k]\setminus\{i\}\) and thus, it is covered by \(\{u_{i},u_{j}\}\). If there is \(X\subseteq S\) covers \(U\) with cardinality at most \(\binom{k}{2}\), then we show that there is a \(k\)-clique in \(G^{\prime}\). Firstly, \(|X\cap E_{i,j}|=1\) for \(1\leq i<j\leq k\). Otherwise, let \(f^{(i)}(0)=f^{(i)}(1)=j\) and for any \(l\in[\log n]\), \((f^{(i)},l)\in U_{i}\) is not covered by \(X\). Now we let \(X\) be the vertices \(e_{i,j}\in E_{i,j}\) for every \(1\leq i<j\leq k\). For each \(i\in[k]\) and distinct \(j,j^{\prime}\in[k]\setminus\{i\}\), we let \(e_{i,j}=\{v,u^{(i)}\}\) and \(e_{i,j^{\prime}}=\{v^{\prime},u^{(j^{\prime})}\}\). We claim that \(v=v^{\prime}\). Otherwise, there must be a bit \(l\in[\log n]\) such that \(\mathbf{b}(v)[l]\
eq\mathbf{b}(v^{\prime})[l]\). Without loss of generality, we assume \(\mathbf{b}(v)[l]=0,\mathbf{b}(v^{\prime})[l]=1\). Now we take \(f^{(i)}\) such that \(f^{(i)}(0)=j^{\prime}\) and \(f^{(i)}(1)=j\). Then \((f^{(i)},l)\) is not covered by \(X\), which is a contradiction. Hence, for every \(i\in[k]\), we could safely take the vertex \(v^{(i)}\in V_{i}\) such that \(v^{(i)}\) is in the edge \(e_{i,j}\in X\cap E_{i,j}\) for arbitrary \(j\) as the \(i\)-th vertex of the \(k\)-clique. The \(C_{n,k}\) outputs \(I^{\prime}\) with at most \(k^{5}n^{2}\log n\) bits where whether \(e_{u^{(i)},vj}\) and \((f^{(i)},l)\) is connected is determined by  
\[\mathsf{bit}_{I}\{e_{u^{(i)},v^{(i)}},(f^{(i)},l)\}= \begin{cases}1,&\text{if }f^{(i)}(\mathbf{b}(u^{(i)})[l])=j\\ 0,&\text{otherwise}\end{cases} \]  
for every \(1\leq i<j\leq k\), \(e_{u^{(i)},v^{(i)}}\in E_{i,j}\) and every \((f^{(i)},l)\in U_{i}\). Hence, \(C_{n,k}\) is with each output gate of depth at most \(3\) and of size at most \(k^{5}n^{2}\log n\).