  We initiate the study of a new parameterization of graph problems. In a
multiple interval representation of a graph, each vertex is associated to at
least one interval of the real line, with an edge between two vertices if and
only if an interval associated to one vertex has a nonempty intersection with
an interval associated to the other vertex. A graph on n vertices is a k-gap
interval graph if it has a multiple interval representation with at most n+k
intervals in total. In order to scale up the nice algorithmic properties of
interval graphs (where k=0), we parameterize graph problems by k, and find FPT
algorithms for several problems, including Feedback Vertex Set, Dominating Set,
Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The
Coloring problem turns out to be W[1]-hard and we design an XP algorithm for
the recognition problem.
