Cover Image

The stochastic block model has the overlap graph property for modularity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhamidi, Shankar, Gamarnik, David, van der Hofstad, Remco, Litvak, Nelly, Pralat, Pawel, Skerman, Fiona, Tousinejad, Yasmin
Format:	Preprint
Published:	2026
Subjects:	Probability Computational Complexity Data Structures and Algorithms Combinatorics Statistics Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
by: Dumas, Maël, et al.
Published: (2022)

The rank of sparse symmetric matrices over arbitrary fields
by: Remco van der Hofstad, et al.
Published: (2024)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Some easy optimization problems have the overlap-gap property
by: Li, Shuangping, et al.
Published: (2024)

The complexity of testing all properties of planar graphs, and the role of isomorphism
by: Basu, Sabyasachi, et al.
Published: (2021)

On the accurate computation of expected modularity in probabilistic networks
by: Shen, Xin, et al.
Published: (2024)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
by: Gamarnik, David, et al.
Published: (2026)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
by: Ducoffe, Guillaume
Published: (2026)

Modularity and partially observed graphs
by: McDiarmid, Colin, et al.
Published: (2021)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

Smoothed analysis for graph isomorphism
by: Anastos, Michael, et al.
Published: (2024)

On the complexity of global Roman domination problem in graphs
by: Reddy, Sangam Balchandar, et al.
Published: (2026)

Planted clique recovery in random geometric graphs
by: Avrachenkov, Konstantin, et al.
Published: (2025)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
by: Prunet, Thibault, et al.
Published: (2023)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
by: Johnson, Matthew, et al.
Published: (2022)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
by: Huang, Neng, et al.
Published: (2024)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

Maximum $k$- vs. $\ell$-colourings of graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2023)

Sequence graphs realizations and ambiguity in language models
by: Khalife, Sammy, et al.
Published: (2024)

Channel allocation revisited through 1-extendability of graphs
by: Busson, Anthony, et al.
Published: (2024)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)

Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
by: Kutner, David C., et al.
Published: (2025)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
by: Apers, Simon, et al.
Published: (2021)

Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
by: Chauhan, Archit, et al.
Published: (2025)

Perfect Matchings and Loose Hamilton Cycles in the Semirandom Hypergraph Model
by: Michael Molloy, et al.
Published: (2025)

Isometric path complexity of graphs
by: Chakraborty, Dibyayan, et al.
Published: (2022)

Neighborhood-Aware Graph Labeling Problem
by: Shahverdikondori, Mohammad, et al.
Published: (2026)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

Lazy Kronecker Product
by: Song, Zhao
Published: (2026)

The Trichotomy of Regular Property Testing
by: Bathie, Gabriel, et al.
Published: (2025)

Can You Link Up With Treewidth?
by: Curticapean, Radu, et al.
Published: (2024)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)