Generalized vertex covering in interval graphs

Given an integer i and an undirected graph G, the generalized i-vertex cover problem is to find a minimum set of vertices such that all cliques in G of size i contain at least one vertex from this set. This problem is known to be NP-complete for chordal graphs when i is part of the input. We present a greedy linear time algorithm for this problem in the case of interval graphs. © 1992.