# On Finding Dense Common Subgraphs

arXiv: https://arxiv.org/abs/1802.06361 · HTML: https://mlsanity.com/paper/1802.06361/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2018.

## Built on by (most cited first, 2 of 2)

- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Jaccard-constrained dense subgraph discovery](https://mlsanity.com/paper/2308.15936/) (2023)

## Abstract (arXiv)

We study the recently introduced problem of finding dense common subgraphs: Given a sequence of graphs that share the same vertex set, the goal is to find a subset of vertices S that maximizes some aggregate measure of the density of the subgraphs induced by S in each of the given graphs. Different choices for the aggregation function give rise to variants of the problem that were studied recently. We settle many of the questions left open by previous works, showing NP-hardness, hardness of approximation, non-trivial approximation algorithms, and an integrality gap for a natural relaxation.