Proportionally dense subgraph of maximum size: complexity and approximation

Cristina Bazgan, Janka Chlebikova, Clément Dallard, Thomas Pontoizeau

Research output: Contribution to journalArticlepeer-review

92 Downloads (Pure)

Abstract

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. We also show that deciding if a PDS is inclusion-wise maximal is co-NP-complete on bipartite graphs. Nevertheless, we present a simple polynomial-time (2-2/(Δ+1))-approximation algorithm for the problem, where Δ is the maximum degree of the graph. Finally, we show that all Hamiltonian cubic graphs with n vertices (except two) have a PDS of size ⌊(2n+1)/3⌋, which we prove to be an upper bound on the size of a PDS in cubic graphs. is the maximum degree of the graph.
Original languageEnglish
Pages (from-to)25-36
Number of pages12
JournalDiscrete Applied Mathematics
Volume270
Early online date22 Jul 2019
DOIs
Publication statusPublished - 1 Nov 2019

Keywords

  • dense subgraph
  • approximation
  • complexity theory
  • Hamiltonian cubic graphs

Fingerprint

Dive into the research topics of 'Proportionally dense subgraph of maximum size: complexity and approximation'. Together they form a unique fingerprint.

Cite this