The following technical report is available from http://aib.informatik.rwth-aachen.de:
The $\lambda$-cluster Problem on Parameterized Interval Graphs George B. Mertzios, Stavros D. Nikolopoulos AIB 2008-08
This paper is concerned with the problem of finding, for a given graph $G$ and a given natural number $\lambda$, a subgraph of $G$ on $\lambda$ vertices with a maximum number of edges. The problem is known as the $\lambda$-cluster problem and is NP-hard on general graphs; it remains NP-hard even when restricted to specific graph classes such as comparability, bipartite, chordal graphs, while it is polynomially solvable on the class of interval graphs. Here, we are interested in investigating how the $\lambda$-cluster problem behaves on input graphs that are ``close'' to interval graphs. For this purpose, we consider the class of modified interval graphs, denoted by interval$\pm ke$, which is the class of graphs obtained from interval graphs by adding at most $k_1$ edges and deleting at most $k_2$ edges, where $k=k_1+k_2$. We show that the $\lambda$-cluster problem is fixed-parameter tractable (FPT) with parameter $k$ on interval$\pm ke$ graphs. In particular, we present a dynamic programming algorithm which computes a $\lambda$-cluster of an $n$-vertex interval$\pm ke$ graph in $O(2^{k_1+2k_2} \cdot n \lambda6)$ time, where $k=k_1+k_2$. Our results imply that the $\lambda$-cluster problem is also FPT on both interval$+ke$ and interval$-ke$ classes of graphs with complexity $O(2^{k} \cdot n \lambda6)$ and $O(2^{2k} \cdot n \lambda6)$ respectively.