# Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
## 6 \(k\)-Trees  
Assume that \(G\) is a graph with \(n\) vertices \(x_{1},x_{2},\ldots,x_{n}\). Let \(i\in\{1,2,\ldots,n\}\) and let \(G_{i}\) be the subgraph \(G[V(G)\setminus\{x_{1},x_{2},\ldots x_{i-1}\}]\). For every \(x\in V(G_{i})\), let \(N_{i}[x]=\{y\mid y\in(N_{G}[x]\setminus\{x_{1},x_{2},\ldots,x_{i-1}\})\}\). If \(N_{i}[x_{i}]\) is a clique for \(1\leq i\leq n\), then the ordering \((x_{1},x_{2},\ldots,x_{n})\) is a _perfect elimination ordering_ (abbreviated as PEO) of \(G\). A graph \(G\) is chordal if and only if \(G\) has a PEO [26]. A chordal graph \(G\) is a \(k\)-tree if and only if either \(G\) is a complete graph of \(k\) vertices or \(G\) has more than \(k\) vertices and there exists a PEO\((x_{1},x_{2},\ldots,x_{n})\) such that \(N_{i}[x_{i}]\) is a clique of \(k\) vertices if \(i=n-k+1\); otherwise, \(N_{i}[x_{i}]\) is a clique of \(k+1\) vertices for \(1\leq i\leq n-k\). Figure 4 shows a 2-tree with the PEO \((v_{1},v_{2},\ldots,v_{13})\). In [3], [PERSON] et al. showed that the MCTP is NP-complete for \(k\)-trees with unbounded \(k\) by proving \(\gamma(G)=\tau_{M}(G)\) for any \(k\)-tree \(G\). However, Figure 4 shows a counterexample that disproves \(\gamma(G)=\tau_{M}(G)\) for any \(k\)-tree \(G\). The graph \(H\) in Figure 4 is a 2-tree with the perfect elimination ordering \((v_{1},v_{2},\ldots,v_{13})\). The set \(\{v_{5},v_{10}\}\) is the minimum dominating set of \(H\) and the set \(\{v_{5},v_{10},v_{11}\}\) is a minimum MCTS of \(H\). A modified NP-completeness proof is therefore desired for the MCTP on \(k\)-tree with unbounded \(k\). Theorem 4.1: _The MCTP and the MCIP are NP-complete for \(k\)-trees with unbounded \(k\)._  
Proof. : The CTP and the CIP are NP-complete for \(k\)-trees with unbounded \(k\)[8]. Since every maximal clique in a \(k\)-tree is also a maximum clique [27], an MCTS is a CTS and an MCIS is a CIS. Hence, the MCTP and the MCIP are NP-complete for \(k\)-trees with unbounded \(k\). Theorem 4.2: _The SCTP is NP-complete for \(k\)-trees with unbounded \(k\)._  
Proof. : Suppose that \(k_{1}\in\mathbb{N}\) and \(G\) is a \(k_{1}\)-tree with \(|V(G)|>k_{1}\). Let \(C(G)=\{C_{1},C_{2},\ldots,C_{\ell}\}\). Since \(G\) is a \(k_{1}\)-tree, \(|C_{i}|=k_{1}+1\) for \(1\leq i\leq\ell\). Let \(Q\) be a clique with \(k_{1}+1\) vertices. Let \(H\) be a graph such that \(V(H)=V(G)\cup Q\) and \(E(H)=E(G)\cup\{(x,y)\mid x,y\in Q\}\cup\{(x,y)\mid x\in Q,y\in V(G)\}\). Let \(X_{i}=C_{i}\cup Q\) be a clique for \(1\leq i\leq\ell\). Clearly, \(C(H)=\{X_{i}\mid 1\leq i\leq\ell\}\). Let \(k_{2}=2k_{1}+1\). Then, \(H\) is a \(k_{2}\)-tree and \(|X_{i}|=k_{2}+1=2k_{1}+2\) for \(1\leq i\leq\ell\). Clearly, we can verify that there exists a minimum-weight SCTF \(h\) of \(H\) of such that \(h(x)=1\) for every \(x\in Q\). Then, \(C_{i}=X_{i}\setminus Q\) contains at least one vertex \(x\) with \(h(x)=1\) for \(1\leq i\leq\ell\). Let \(S=\{x\mid x\in V(H)\setminus Q\) and \(h(x)=1\}\). Then, \(S\) is a CTS of \(G\). Since \(\tau_{\mathrm{C}}^{\varepsilon}(H)=|Q|+2|S|-|V(G)|\), we have \(|Q|+2\tau_{\mathrm{C}}(G)-|V(G)|\leq\tau_{\mathrm{C}}^{\varepsilon}(H)\). Assume that \(D\) is a minimum CTS of \(G\). Let \(f\) be a function of \(H\) whose domain is \(V(H)\) and range is \(\{-1,1\}\), and (1) \(f(x)=1\) for every \(x\in Q\), (2) \(f(x)=1\) for every \(x\in D\), and (3) \(f(x)=-1\) for every \(x\in V(G)\setminus D\). Each maximal clique of \(H\) has at least \(k_{1}+2\) vertices with the function value 1. Therefore, \(f\) is an SCTF. We have \(\tau_{\mathrm{C}}^{\varepsilon}(H)\leq|Q|+2\tau_{\mathrm{C}}(G)-|V(G)|\). Following what we have discussed above, we know that \(\tau_{\mathrm{C}}^{\varepsilon}(H)=|Q|+2\tau_{\mathrm{C}}(G)-|V(G)|\). The theorem therefore holds by the NP-completeness of the CTP for \(k\)-trees [8]. Theorem 4.3: _Suppose that \(\kappa\in\mathbb{N}\) the \(\kappa\)-FCTP is NP-complete on \(k\)-trees with unbounded \(k\)._  
Proof. : Assume that \(k_{1}\in\mathbb{N}\) and \(G\) is a \(k_{1}\)-tree with \(|V(G)|>k_{1}\).