Generalized vertex covering in interval graphs (Q1199467)

The following decision problem is treated in the paper: Given a graph \(G\) and two integers \(i\geq 2\), \(k\geq 1\), is it possible to find \(k\) vertices of the graph such that any complete subgraph of \(G\) with \(i\) vertices contains (at least) one of these distinguished vertices. This problem is NP-complete even for chordal graphs. In this paper a greedy linear-time algorithm for interval graphs is presented --- in fact the algorithm solves the corresponding optimization problem. In particular the minimum vertex cover problem \((i=2)\) and the minimum feedback vertex set problem \((i=3)\) can be solved in linear time for interval graphs.