Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs

摘要

The densest k-subgraph problem asks for a k-vertex subgraph with the maximum number of edges. This problem is NP-hard on bipartite graphs, chordal graphs, and planar graphs. A 3-approximation algorithm is known for chordal graphs. We present 3/2-approximation algorithms for proper interval graphs and bipartite permutation graphs. The latter result relies on a new characterisation of bipartite permutation graphs which may be of independent interest.