# Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
## 3 Clique Perfect Graphs  
Let \(\mathcal{G}\) be the set of all induced subgraphs of \(\mathcal{G}\). If \(\tau_{\mathbb{C}}(H)=\alpha_{\mathbb{C}}(H)\) for every \(H\in\mathcal{G}\), then \(G\) is _clique perfect_. In this section, we study the \(\{k\}\)-CTP for clique perfect graphs and the SCTP for balanced graphs. Lemma 4.: _Let \(G\) be such a graph that \(\tau_{\mathbb{C}}(G)=\alpha_{\mathbb{C}}(G)\). Then, \(\tau_{\mathbb{C}}^{\{k\}}(G)=k\tau_{\mathbb{C}}(G)\)._  
Proof. : Assume that \(D\) is a minimum STS of \(G\). Then, \(|D|=\tau_{\mathbb{C}}(G)\). Let \(x\in V(G)\) and let \(f\) be a function whose domain is \(V(G)\) and range is \(\{0,1,\ldots,k\}\), and \(f(x)=k\) if \(x\in D\); otherwise, \(f(x)=0\). Clearly, \(f\) is a \(\{k\}\)-CTF of \(G\). We have \(\tau_{\mathbb{C}}^{\{k\}}(G)\leq k\tau_{\mathbb{C}}(G)\). Assume that \(f\) is a minimum-weight \(\{k\}\)-CTF of \(G\). Then, \(f(V(G))=\tau_{\mathbb{C}}^{\{k\}}(G)\) and \(f(C)\geq k\) for every \(C\in C(G)\). Let \(S=\{C_{1},C_{2},\ldots,C_{\ell}\}\) be a maximum CIS of \(G\). We know that \(|S|=\ell=\alpha_{\mathbb{C}}(G)\) and \(\sum_{i=1}^{\ell}f(C_{i})\leq f(V(G))\). Therefore, \(k\tau_{\mathbb{C}}(G)=k\alpha_{\mathbb{C}}(G)=k\ell\leq\sum_{i=1}^{\ell}f(C_{ i})\leq f(V(G))=\tau_{\mathbb{C}}^{\{k\}}(G)\). Following what we have discussed above, we know that \(\tau_{\mathbb{C}}^{\{k\}}(G)=k\tau_{\mathbb{C}}(G)\). Theorem 2.: _If a graph \(G\) is clique perfect, \(\tau_{\mathbb{C}}^{\{k\}}(G)=k\tau_{\mathbb{C}}(G)\)._  
Proof. : Since \(G\) is clique perfect, \(\tau_{\mathbb{C}}(G)=\alpha_{\mathbb{C}}(G)\). Hence, the theorem holds by Lemma 4. Corollary 2.: _The \(\{k\}\)-CTP is polynomial-time solvable for distance-hereditary graphs, balanced graphs, strongly chordal graphs, comparability graphs, and chordal graphs without odd sums._  
Proof. : Distance-hereditary graphs, balanced graphs, strongly chordal graphs, comparability graphs, and chordal graphs without odd sums are clique perfect, and the CTP can be solved in polynomial time for them [10; 11; 12; 13; 14]. The corollary therefore holds. Definition 8.: _Suppose that \(R\) is a function whose domain is \(C(G)\) and range is \(\{0,1,\ldots,\omega(G)\}\). If \(R(C)\leq|C|\) for every \(C\in C(G)\), then \(R\) is a clique-size restricted function (abbreviated as CSRF) of \(G\). A set \(D\subseteq V(G)\) is an \(R\)-clique transversal set (abbreviated as \(R\)-CTS) of \(G\) if \(R\) is a CSRF of \(G\) and \(|D\cap\mathbb{C}|\geq R(\mathbb{C})\) for every \(C\in C(G)\). Let \(\tau_{R}(G)=min\left\{|D|\mid D\text{ is an $R$-CTS of }G\right\}\). The generalized clique transversal problem (abbreviated as GCTP) is to find a minimum \(R\)-CTS for a graph \(G\) with a CSRF \(R\). Lemma 5: _Let \(G\) be a graph with a CSRF \(R\). If \(R(\mathbb{C})=\lceil(|C|+1)/2\rceil\) for every \(C\in C(G)\), then \(\tau_{\mathbb{C}}^{s}(G)=2\tau_{R}(G)-n\)._  
Proof: Assume that \(D\) is a minimum \(R\)-CTS of \(G\). Then, \(|D|=\tau_{R}(G)\). Let \(x\in V(G)\) and let \(f\) be a function of \(G\) whose domain is \(V(G)\) and range is \(\{-1,1\}\), and \(f(x)=1\) if \(x\in D\); otherwise, \(f(x)=-1\). Since \(|D\cap C|\geq\lceil(|C|+1)/2\rceil\) for every \(C\in C(G)\), there are at least \(\lceil(|C|+1)/2\rceil\) vertices in \(C\) with the function value \(1\). Therefore, \(f(C)\geq 1\) for every \(C\in C(G)\), and \(f\) is an SCTF of \(G\). Then, \(\tau_{\mathbb{C}}^{s}(G)\leq 2\tau_{R}(G)-n\). Assume that \(h\) is a minimum-weight SCTF of \(G\). Clearly, \(h(V(G))=\tau_{\mathbb{C}}^{s}(G)\). Since \(h(C)\geq 1\) for every \(C\in C(G)\), \(C\) contains at least \(\lceil(|C|+1)\rceil/2\) vertices with the function value \(1\). Let \(D=\{x\mid h(x)=1,x\in V(G)\}\). The set \(D\) is an \(R\)-CTS of \(G\). Therefore, \(2\tau_{R}(G)-n\leq 2|D|-n=\tau_{\mathbb{C}}^{s}(G)\). Hence, we have \(\tau_{\mathbb{C}}^{s}(G)=2\tau_{R}(G)-n\).