The k-Sparsest Subgraph in (proper) Interval Graphs
SpeakerMarin Bougeret
Given a graph G=(V, E) and an integer k, the k-Sparsest Subgraph (k-SS) problem asks for a set of k vertices in G which induce the minimum number of edges. As a generalization of the classical Independent Set problem, k-SS is W[1]-hard as well as inapproximable in general graphs. In this talk we provide an FPT algorithm in interval graphs and a Polynomial-Time Approximation Scheme in proper interval graphs, both using dynamic programming.