Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
Andreas Göbel, Janosch Ruff, Leon Schiller
We study efficient algorithms for recovering cliques in dense random intersection graphs (RIGs). In this model, cliques of size approximately are randomly plante…
cs.DS2025
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…