An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

We investigate the computational complexity of the Densestkk-Subgraph problem, where the input is an undirected graph G=(V,E)G=(V,E) and one wants to find a subgraph on exactly  kk vertices with the maximum number of edges. We extend previous work on Densestkk-Subgraph by studying its parameterized complexity for parameters describing the sparseness of the input graph and for parameters related to the solution size  kk.On the positive side, we show that, when fixing some constant minimum density  μμ of the sought subgraph, Densestkk-Subgraph becomes fixed-parameter tractable with respect to either of the parameters maximum degree of  GG and  hh-index of  GG. Furthermore, we obtain a fixed-parameter algorithm for Densestkk-Subgraph with respect to the combined parameter “degeneracy of  GG and |V|−k|V|−k”.On the negative side, we find that Densestkk-Subgraph is W[1]-hard with respect to the combined parameter “solution size  kk and degeneracy of  GG”. We furthermore strengthen a previous hardness result for  Densestkk-Subgraph (Cai, 2008) by showing that for every fixed  μμ,  0<μ<10<μ<1, the problem of deciding whether  GG contains a subgraph of density at least  μμ is W[1]-hard with respect to the parameter  |V|−k|V|−k.Our positive results are obtained by an algorithmic framework that can be applied to a wide range of Fixed-Cardinality Optimization  problems.