2018/12/30 by Silwal, Sandeep, Tidor, Jonathan
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1812.11564
In the framework of graph property testing, we study the problem of determining if a graph admits a cluster structure. We say that a graph is (k, ϕ)-clusterable if it can be partitioned into at most k parts such that each part has conductance at least ϕ. We present an algorithm that accepts all graphs that are (2, ϕ)-clusterable with probability at least \frac23 and rejects all graphs that are ε-far from (2, ϕ^*)-clusterable for ϕ^* ≤ μϕ2 ε2 with probability at least \frac23 where μ> 0 is a parameter that affects the query complexity. This improves upon the work of Czumaj, Peng, and Sohler by removing a log n factor from the denominator of the bound on ϕ^* for the case of k=2. Our work was concurrent with the work of Chiplunkar et al.\@ who achieved the same improvement for all values of k. Our approach for the case k=2 relies on the geometric structure of the eigenvectors of the graph Laplacian and results in an algorithm with query complexity O(n1/2+O(1)μ ⋅ poly(1/ε, 1/ϕ,log n)).