# Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
## 1 Introduction  
Every graph \(G=(V,E)\) in this paper is finite, undirected, connected, and has at most one edge between any two vertices in \(G\). We assume that the vertex set \(V\) and edge set \(E\) of \(G\) contain \(n\) vertices and \(m\) edges. They can also be denoted by \(V(G)\) and \(E(G)\). A graph \(G^{\prime}=(V^{\prime},E^{\prime})\) is an _induced subgraph_ of \(G\) denoted by \(G[V^{\prime}]\) if \(V^{\prime}\subseteq V\) and \(E^{\prime}\) contains all the edge \((x,y)\in E\) for \(x,y\in V^{\prime}\). Two vertices \(x,y\in V\) are _adjacent_ or _neighbors_ if \((x,y)\in E\). The sets \(N_{G}(x)=\{y\mid(x,y)\in E\}\) and \(N_{G}[x]=N_{G}(x)\cup\{x\}\) are the _neighborhood_ and _closed neighborhood_ of a vertex \(x\) in \(G\), respectively. The number \(deg_{G}(x)=|N_{G}(x)|\) is the _degree_ of \(x\) in \(G\). If \(deg_{G}(x)=k\) for every \(x\in V\), then \(G\) is _\(k\)-regular_. Particularly, _cubic graphs_ are an alternative name for \(3\)-regular \(G\). A subset \(S\) of \(V\) is _clique_ if \((x,y)\in E\) for \(x,y\in S\). Let \(Q\) be a clique of \(G\). If \(Q(\cap Q^{\prime}\
eq Q\) for any other clique \(Q^{\prime}\) of \(G\), then \(Q\) is a _maximal_ clique. We use \(C(G)\) to represent the set \(\{C\mid C\) is a maximal clique of \(G\}\). A clique \(S\in C(G)\) is a _maximum_ clique if \(|S|\geq|S^{\prime}|\) for every \(S^{\prime}\in C(G)\). The number \(\omega(G)=\max\{|S|\mid S\in C(G)\}\) is the _clique number_ of \(G\). A set \(D\subseteq V\) is a _clique transversal set_ (abbreviated as CTS) of \(G\) if \(|C\cap D|\geq 1\) for every \(C\in C(G)\). The number \(\tau_{C}(G)=\min\{|S|\mid S\) is a CTS of \(G\}\) is the _clique transversal number_ of \(G\). The _clique transversal problem_ (abbreviated as CTP) is to find a minimum CTS for a graph. A set \(S\subseteq C(G)\) is a _clique independent set_ (abbreviated as CIS) of \(G\) if \(|S|=1\) or \(|S|\geq 2\) and \(C\cap C^{\prime}=\emptyset\) for \(C,C^{\prime}\in S\). The number \(\alpha_{C}(G)=\max\{|S|\mid S\) is a CIS of \(G\}\) is the _clique independence number_ of \(G\). The _clique independence problem_ (abbreviated as CIP) is to find a maximum CIS for a graph. The CTP and the CIP have been widely studied. Some studies on the CTP and the CIP consider imposing some additional constraints on CTS or CIS, such as the _maximum-clique independence problem_ (abbreviated as MCIP), the _k-fold clique transversal problem_ (abbreviated as \(k\)-FCTP), and the _maximum-clique transversal problem_ (abbreviated as MCTP). **Definition 1** ([1, 2]). : _Suppose that \(k\in\mathbb{N}\) is fixed and \(G\) is a graph. A set \(D\subseteq V(G)\) is a \(k\)-fold clique transversal set (abbreviated as \(k\)-FCTS) of \(G\) if \(|C\cap D|\geq k\) for \(C\in C(G)\). The number \(\tau_{C}^{k}(G)=min\{|S|\mid S\) is a \(k\)-FCTS of \(G\}\) is the \(k\)-fold clique transversal number of \(G\). The \(k\)-FCTP is to find a minimum \(k\)-FCTS for a graph._  
**Definition 2** ([3, 4]). : _Suppose that \(G\) is a graph. A set \(D\subseteq V(G)\) is a maximum-clique transversal set (abbreviated as MCTS) of \(G\) if \(|C\cap D|\geq 1\) for \(C\in C(G)\) with \(|C|=\omega(G)\). The number \(\tau_{M}(G)=min\{|S|\mid S\) is an MCTS of \(G\}\) is the maximum-clique transversal number of \(G\). The MCTP is to find a minimum MCTS for a graph. A set \(S\subseteq C(G)\) is a maximum-clique independent set (abbreviated as MCIS) of \(G\) if \(|C|=\omega(G)\) for \(C\in S\) and \(C\cap C^{\prime}=\emptyset\) for \(C,C^{\prime}\in S\). The number \(\alpha_{M}(G)=max\{|S|\mid S\) is an MCIS of \(G\}\) is the maximum-clique independence number of \(G\). The MCIP is to find a maximum MCIS for a graph._  
The \(k\)-FCTP on balanced graphs can be solved in polynomial time [2]. The MCTP has been studied in [3] for several well-known graph classes and the MCIP is polynomial-time solvable for any graph \(H\) with \(\tau_{M}(H)=\alpha_{M}(H)\)[4]. Assume that \(Y\subseteq\mathbb{R}\) and \(f:X\to Y\) is a function.