Thumbnail - Request a copy

Proportionally dense subgraph of maximum size: Complexity and approximation

Bazgan, Cristina; Chlebíková, Janka; Dallard, Clément; Pontoizeau, Thomas (2019), Proportionally dense subgraph of maximum size: Complexity and approximation, Discrete Applied Mathematics, 270, p. 25-36. 10.1016/j.dam.2019.07.010

Type
Article accepté pour publication ou publié
Date
2019
Journal name
Discrete Applied Mathematics
Volume
270
Publisher
Elsevier
Pages
25-36
Publication identifier
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chlebíková, Janka
School of Computing [Portsmouth]
Dallard, Clément
School of Computing [Portsmouth]
Pontoizeau, Thomas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is APX-hard on split graphs, and NP-hard on bipartite graphs.
Subjects / Keywords
Dense subgraph; Approximation; Complexity; Hamiltonian cubic graphs