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 γ-complete graph model, which is based on relaxing the degree constraint of the clique model, that is G[S] is a γ-complete graph, with γ∈(0,1], if and only if every vertex of S has degree at least γ(|S|−1) in G[S]. In this contribution, we investigate the complexity of the problem that asks for the γ-complete subgraph of maximum order (that is, maximum number of vertices). We show that the problem is W[1]-hard for [Formula presented] when 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.

(2021). Hardness and tractability of the γ-Complete Subgraph problem [journal article - articolo]. In INFORMATION PROCESSING LETTERS. Retrieved from http://hdl.handle.net/10446/200856

Hardness and tractability of the γ-Complete Subgraph problem

Dondi, Riccardo;Hosseinzadeh, Mohammad Mehdi
2021

Abstract

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 γ-complete graph model, which is based on relaxing the degree constraint of the clique model, that is G[S] is a γ-complete graph, with γ∈(0,1], if and only if every vertex of S has degree at least γ(|S|−1) in G[S]. In this contribution, we investigate the complexity of the problem that asks for the γ-complete subgraph of maximum order (that is, maximum number of vertices). We show that the problem is W[1]-hard for [Formula presented] when 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.
articolo
Baril, Ambroise; Dondi, Riccardo; Hosseinzadeh, Mohammad Mehdi
(2021). Hardness and tractability of the γ-Complete Subgraph problem [journal article - articolo]. In INFORMATION PROCESSING LETTERS. Retrieved from http://hdl.handle.net/10446/200856
File allegato/i alla scheda:
File Dimensione del file Formato  
IPL2021.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 295.91 kB
Formato Adobe PDF
295.91 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/200856
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact