Approximation algorithms for clique transversals on some graph classes

作者：Lin Min Chih; Vasiliev Saveliy^*

来源：Information Processing Letters, 2015, 115(9): 667-670.

DOI：10.1016/j.ipl.2015.04.003

• Approximation algorithms
• Clique transversal
• Graph classes
• NP-hard

Given a graph G = (V. E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique transversal is NP-hard for the following classes: planar, line and bounded degree graphs. For line graphs we present a 3-approximation for the unweighted case and a 4-approximation for the weighted case with nonnegative weights; a inverted right perpendicular(G) + 1)/2inverted left perpendicular-approximation for bounded degree graphs and a 3-approximation for planar graphs.

• 出版日期2015-9