On the parameterized complexity of some optimization problems related to multiple-interval graphs

We show that for any constant t≥2, k-Independent Set and k-Dominating Set in t-track interval graphs are W[1]-hard. This settles an open question recently raised by Fellows, Hermelin, Rosamond, and Vialette. We also give an FPT algorithm for k-Clique in t-interval graphs, parameterized by both k and t, with running time , where n is the number of vertices in the graph. This slightly improves the previous FPT algorithm by Fellows, Hermelin, Rosamond, and Vialette. Finally, we use the W[1]-hardness of k-Independent Set in t-track interval graphs to obtain the first parameterized intractability result for a recent bioinformatics problem called Maximal Strip Recovery (MSR). We show that MSR-d is W[1]-hard for any constant d≥4 when the parameter is either the total length of the strips, or the total number of adjacencies in the strips, or the number of strips in the solution.