PTAS for Densest k-Subgraph in Interval Graphs

Abstract

Given an interval graph and integer k, we consider the problem of finding a subgraph of size k with a maximum number of induced edges, called densest k -subgraph problem in interval graphs. This problem is NP-hard even for chordal graphs (Perl and Corneil in Discret Appl Math 9(1):27–39, 1984), and there is probably no PTAS for general graphs (Khot and Subhash in SIAM J Comput 36(4):1025–1071, 2006). However, the exact complexity status for interval graphs is a long-standing open problem (Perl and Corneil in Discret Appl Math 9(1):27–39, 1984), and the best known approximation result is a $$3$$3-approximation algorithm (Liazi et al. in Inf Process Lett 108(1):29–32, 2008). We shed light on the approximation complexity of finding a densest k-subgraph in interval graphs by presenting a polynomial-time approximation scheme (PTAS), that is, we show that there is an (1+ϵ)-approximation algorithm for any ϵ>0, which is the first such approximation scheme for the densest k-subgraph problem in an important graph class without any further restrictions.