EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Testing Cluster Structure of Graphs

Artur Czumaj, Pan Peng, Christian Sohler

ACM Transactions on Algorithms · 31.07.2026 · 22 (3) · 1-32

DOI: 10.1145/3807605 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 03.06.2026. Verfasst von Artur Czumaj und 2 weiteren Autor:innen. Die Arbeit nennt 45 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Centre for Discrete Mathematics and its Applications, Engineering and Physical Sciences Research Council, ERC.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the problem of recognizing the spectral cluster structure of a graph in the framework of property testing in the bounded degree model. A graph is defined to be \((k,\phi_{\textrm{in}},\phi_{\textrm{out}})\) - clusterable , if it can be partitioned into no more than \( k \) parts, such that the (inner) conductance of the induced subgraph on each part is at least \(\phi_{\textrm{in}}\) and the (outer) conductance of each part is at most \(\phi_{\textrm{out}}\) . Our main result is a sublinear algorithm with the running time \(\widetilde{O}_{d,k}(\sqrt{n}\cdot\mathrm{poly}(\phi,1/\varepsilon))\) that takes as input an \( n \) -vertex graph with maximum degree bounded by \( d \) , parameters \( k \) , \(\phi\) , \(\varepsilon\) , and with probability at least \(\frac{2}{3}\) , accepts the graph if it is \((k,\phi,O_{d,k}(\varepsilon^{4}\phi^{2}))\) -clusterable, and rejects the graph if it is \(\varepsilon\) -far from \((k,\phi^{*},\psi^{*})\) -clusterable for \(\phi^{*}=O_{d,k}(\frac{\phi^{2}\varepsilon^{4}}{\log n})\) and any \(\psi^{*}\geq 0\) . By the lower bound of \(\Omega(\sqrt{n})\) on the number of queries needed for testing graph expansion, which corresponds to \(k=1\) in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors.

Förderung

  • Centre for Discrete Mathematics and its Applications
  • Engineering and Physical Sciences Research Council
  • ERC
  • NSFC

Zitieren

APA

Czumaj, A., Peng, P., & Sohler, C. (2026). Testing Cluster Structure of Graphs. ACM Transactions on Algorithms, 22(3), 1-32. https://doi.org/10.1145/3807605

Vancouver

Czumaj A, Peng P, Sohler C. Testing Cluster Structure of Graphs. ACM Transactions on Algorithms. 2026;22(3):1-32. doi:10.1145/3807605

BibTeX
@article{Czumaj2026,
  author = {Czumaj, Artur and Peng, Pan and Sohler, Christian},
  title = {Testing Cluster Structure of Graphs},
  journal = {ACM Transactions on Algorithms},
  year = {2026},
  volume = {22},
  number = {3},
  pages = {1--32},
  doi = {10.1145/3807605}
}
Kostenlos starten →