The k densest subgraph of an interval graph
Consider a graph G and an integer k. The k densest subgraph problem consists in finding a subgraph of G with k nodes and a maximum number of edges. The problem is known to be NP-Hard for chordal graph but is open for interval graph (even open for proper interval graphs in which no interval is included in another).