Abstract
Given a simple undirected graph G = (V, E) and an integer k ≤ |V|, the k-sparsest subgraph problem asks for a set of k vertices that induce the minimum number of edges. As a generalization of the classical independent set problem, k-sparsest subgraph cannot ad- mit (unless P = NP) neither an approximation nor an FPT algorithm (parameterized by the number of edges in the solution) in all graph classes where independent set is NP-hard. Thus, it appears natural to investigate the approximability and fixed parameterized tractability of k-sparsest subgraph in graph classes where independent set is polynomial, such as subclasses of perfect graphs. In this paper, we first present a simple greedy tight 2-approximation algorithm in proper interval graphs, and then we use dynamic programming to design a PTAS in proper interval graph and an FPT algorithm in interval graphs (parameterized by the number of edges in the solution).