Skip to content

Proportionally dense subgraph of maximum size: complexity and approximation

Research output: Contribution to journalArticle

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
JournalDiscrete Applied Mathematics
Publication statusAccepted for publication - 10 Jul 2019

Documents

  • Proportionally dense subgraph

    Rights statement: The embargo end date of 2050 is a temporary measure until we know the publication date. Once we know the publication date the full text of this article will be able to view shortly afterwards.

    Accepted author manuscript (Post-print), 482 KB, PDF-document

    Due to publisher’s copyright restrictions, this document is not freely available to download from this website until: 1/01/50

    Licence: CC BY-NC-ND

Related information

Relations Get citation (various referencing formats)

ID: 14778573