Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs

A clique-transversal set S of a graph G is a subset of vertices intersecting all the cliques of G, where a clique is a complete subgraph maximal under inclusion and having at least two vertices. A clique-independent set of the graph G is a set of pairwise disjoint cliques of G. The clique-transversal number  τC(G)τC(G) of G is the cardinality of the smallest clique-transversal set in G and the clique-independence number  αC(G)αC(G) of G is the cardinality of the largest clique-independent set in G  . This paper proves that determining τC(G)τC(G) and αC(G)αC(G) is NP-complete for a cubic planar graph G   of girth 3. Further we propose two approximation algorithms for determining τC(G)τC(G) and αC(G)αC(G) in a cubic graph G.

► The clique-transversal problem is NP-complete for cubic planar graphs.
► The clique-independent set problem is NP-complete for cubic planar graphs.
► We propose two approximation algorithms for the two problems.