Searching for dense subsets in a graph via the partition function

2018/07/05 by Alexander Barvinok, Barvinok, Alexander, Anthony Della Pella +1
Computer Science · Mathematics · #05C31 #05C69 #05C85 #68Q25 #82B20 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1807.02054

openalex publication_date 2018/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a set S of vertices of a graph G, we define its density 0 ≤ σ(S) ≤ 1 as the ratio of the number of edges of G spanned by the vertices of S to |S| \choose 2. We show that, given a graph G with n vertices and an integer m, the partition function ∑_S exp\ γm σ(S) \, where the sum is taken over all m-subsets S of vertices and 0 < γ<1 is fixed in advance, can be approximated within relative error 0 < ε< 1 in quasi-polynomial n^{O(ln m - ln ε)} time. We discuss numerical experiments and observe that for the random graph G(n, 1/2) one can afford a much larger γ, provided the ratio n/m is sufficiently large.

Related

• Computing the partition function for cliques in a graph
• Dense Graph Partitioning on sparse and dense graphs
• Partition functions for dense instances of combinatorial enumeration\n problems
• Computing the partition function for graph homomorphisms with multiplicities
• On Finding Dense Common Subgraphs