2026-07-20T05:08:26Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:22869 2025-10-02T13:35:58Z ddc:004 open_access
Approximating Densest Subgraph in Geometric Intersection Graphs Har-Peled, Sariel Rahul, Saladi Geometric intersection graphs Densest subgraph Range searching Approximation algorithms For an undirected graph 𝖦 = (𝖡, 𝖀), with n vertices and m edges, the densest subgraph problem, is to compute a subset S βŠ† 𝖡 which maximizes the ratio |𝖀_S|/|S|, where 𝖀_S βŠ† 𝖀 is the set of all edges of 𝖦 with endpoints in S. The densest subgraph problem is a well studied problem in computer science. Existing exact and approximation algorithms for computing the densest subgraph require Ξ©(m) time. We present near-linear time (in n) approximation algorithms for the densest subgraph problem on implicit geometric intersection graphs, where the vertices are explicitly given but not the edges. As a concrete example, we consider n disks in the plane with arbitrary radii and present two different approximation algorithms. As a by-product, we show a reduction from (shallow) range-reporting to approximate counting/sampling which seems to be new and is useful for other problems such as independent query sampling. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Sariel Har-Peled and Saladi Rahul 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.43 urn:nbn:de:0030-drops-228697 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.43 eng https://creativecommons.org/licenses/by/4.0/legalcode