Hardness and tractability of the γ-Complete Subgraph problem

Finding cohesive subgraphs is a fundamental problem for the analysis of graphs. Clique is a classical model of cohesive subgraph, but several alternative definitions have been given in the literature. In this paper we consider the gamma-complete graph model, which is based on relaxing the degree constraint of the clique model, that is G[S] is a gamma-complete graph, with gamma is an element of (0, 1], if and only if every vertex of Shas degree at least gamma(vertical bar S vertical bar - 1) in G[S]. In this contribution, we investigate the complexity of the problem that asks for the gamma-complete subgraph of maximum order (that is, maximum number of vertices). We show that the problem is W[1]-hard for 1/2 <= gamma< 1when the parameter is order of the subgraph. Moreover, we show that the problem is fixed-parameter tractable when parameterized by the h-index of the input graph, thus solving an open question in the literature. (c) 2021 Elsevier B.V. All rights reserved.