Approximation Algorithms for Intersection Graphs
We study three complexity parameters that, for each vertex v, are an upper bound for the number of cliques that are sufficient to cover a subset S(v) of its neighbors. We call a graph k-perfectly groupable if S(v) consists of all neighbors, k-simplicial if S(v) consists of the neighbors with a higher number after assigning distinct numbers to all vertices, and k-perfectly orientable if S(v) consists of the endpoints of all outgoing edges from v for an orientation of all edges. These parameters measure in some sense how chordal-like a graph isthe last parameter was not previously considered in literature. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approximation ratio for many NP-hard problems, when restricted to graphs for which at least one of the three complexity parameters is bounded by a constant. As applications we present approximation algorithms with constant approximation ratio for maximum weighted independent set, minimum (independent) dominating set, minimum vertex coloring, maximum weighted clique, and minimum clique partition for large classes of intersection graphs.
intersection graphs np-hard problems parameterized approximation algorithms graph algorithms