# Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
## 4 Split Graphs
As stated in Definition 9, \(I\) can be partitioned into \(S=\{s_{i}\mid 1\leq i\leq\ell\}\) and \(Y=\{y_{i}\mid 1\leq i\leq p+\ell+1\}\), and \(C\) can be partitioned into \(U=\{u_{i}\mid 1\leq i\leq p\}\) and \(X=\{x_{i}\mid 1\leq i\leq p+\ell+1\}\). Assume that \(f\) is a minimum-weight SDF of \(G\). For each \(y_{i}\in Y\), \(|N_{G}[y_{i}]|=2\) and \(y_{i}\) is adjacent to only the vertex \(x_{i}\in X\). Then, \(f(x_{i})=f(y_{i})=1\) for \(1\leq i\leq p+\ell+1\). Since \(C=U\cup X\) and \(|U|=p\), we know that \(f(C)=f(U)+f(X)\geq(-p)+(p+\ell+1)\geq\ell+1\). Figure 3: A split graph \(G\) with one of its partitions indicated. Notice that \(f(N_{G}[y])\geq 1\) and \(N_{G}[y]\in C(G)\) for every \(y\in I\). Therefore, \(f\) is also an SCTF of \(G\). We have \(\tau_{\mathbb{C}}^{s}(G)\leq\gamma_{s}(G)\). Assume that \(h\) is a minimum-weight SCTF of \(G\). For each \(y_{i}\in Y\), \(|N_{G}[y_{i}]|=2\) and \(y_{i}\) is adjacent to only the vertex \(x_{i}\in X\). Then, \(h(x_{i})=h(y_{i})=1\) for \(1\leq i\leq p+\ell+1\). Consider the vertices in \(I\). Since \(N_{G}[y]\in C(G)\) for every \(y\in I\), \(h(N_{G}[y])\geq 1\). We now consider the vertices in \(C\). Recall that \(C=U\cup X\). Let \(u_{i}\in U\). Since \(|U|=p\) and \(|S|=\ell\), we know that \(h(N_{G}[u_{i}])=h(U)+h(X)+h(N_{G}[u_{i}]\cap S)\geq(-p)+(p+\ell+1)+(-\ell)\geq 1\). Let \(x_{i}\in X\). Then, \(h(N_{G}[x_{i}])=h(U)+h(X)+h(y_{i})+h(s_{i})\geq(-p)+(p+\ell+1)+1-1\geq\ell+1\). Therefore, \(h\) is also an SDF of \(G\). We have \(\gamma_{s}(G)\leq\tau_{\mathbb{C}}^{s}(G)\). Following what we have discussed above, we have \(\tau_{\mathbb{C}}^{s}(G)=\gamma_{s}(G)\). The proof for \(\tau_{\mathbb{C}}^{-}(G)=\gamma^{-}(G)\) is analogous to that for \(\tau_{\mathbb{C}}^{s}(G)=\gamma_{s}(G)\). Hence, the theorem holds for any \(H_{1}\)-split graphs. Theorem 4.2: _The SDP on \(H_{1}\)-split graphs is NP-complete._  
Proof. : We reduce the (3,2)-_hitting set problem_ to the SDP on \(H_{1}\)-split graphs. Let \(U=\{u_{i}\mid 1\leq i\leq p\}\) and let \(\mathcal{C}=\{C_{1},C_{2},\ldots,C_{\ell}\}\) such that \(C_{i}\subseteq U\) and \(|C_{i}|=3\) for \(1\leq i\leq\ell\). A (3,2)-hitting set for the instance \((U,\mathcal{C})\) is a subset \(U^{\prime}\) of \(U\) such that \(|C_{i}\cap U^{\prime}|\geq 2\) for \(1\leq i\leq\ell\). The (3,2)-hitting set problem is to find a minimum (3,2)-hitting set for any instance \((U,\mathcal{C})\). The (3,2)-hitting set problem is NP-complete [17]. Consider an instance \((U,\mathcal{C})\) of the (3,2)-hitting set problem. Let \(S=\{s_{i}\mid 1\leq i\leq\ell\}\), \(X=\{x_{i}\mid 1\leq i\leq p+\ell+1\}\), and \(Y=\{y_{i}\mid 1\leq i\leq p+\ell+1\}\). We construct an \(H_{1}\)-split graph \(G=(I,C,E)\) by the following steps. 1. Let \(I=S\cup Y\) be an independent set and let \(C=U\cup X\) be a clique. 2. For each vertex \(s_{i}\in S\), a vertex \(u\in U\) is connected to \(s_{i}\) if \(u\in C_{i}\). 3. For \(1\leq i\leq p+\ell+1\), the vertex \(y_{i}\) is connected to the vertex \(x_{i}\). 4. For \(1\leq i\leq\ell\), the vertex \(s_{i}\) is connected to the vertex \(x_{i}\). Let \(\tau_{\mathbb{H}}(3,2)\) be the minimum cardinality of a (3,2)-hitting set for the instance \((U,\mathcal{C})\). Assume that \(U^{\prime}\) is a minimum (3,2)-hitting set for the instance \((U,\mathcal{C})\). Then, \(|U^{\prime}|=\tau_{\mathbb{H}}(3,2)\). Let \(f\) be a function whose domain is \(V(G)\) and range is \(\{-1,1\}\), and \(f(v)=1\) if \(v\in X\cup Y\cup U^{\prime}\) and \(f(v)=-1\) if \(v\in S\cup(U\setminus U^{\prime})\). Clearly, \(f\) is an SDF of \(G\). We have \(\gamma_{s}(G)\leq 2(p+\ell+1)+|U^{\prime}|-\ell-(p-|U^{\prime}|)=p+\ell+2\tau_{ \mathbb{H}}(3,2)+2\). Assume that \(f\) is minimum-weight SDF of \(G\). For each \(y_{i}\in Y\), \(|N_{G}[y_{i}]|=2\) and \(y_{i}\) is adjacent to only the vertex \(x_{i}\in X\). Then, \(f(x_{i})=f(y_{i})=1\) for \(1\leq i\leq p+\ell+1\). For any vertex \(v\in X\cup Y\cup U\), \(f(N_{\mathbb{C}}[v])\geq 1\) no matter what values the function \(f\) assigns to the vertices in \(U\) or in \(S\).