More Like this

1. Finding a planted clique by adaptive probing

   https://doi.org/10.30757/ALEA.v17-30  

   Racz, Miklos Z; Schiffer, Benjamin (August 2020, Alea)

   null (Ed.)

   We consider a variant of the planted clique problem where we are allowed unbounded computational time but can only investigate a small part of the graph by adaptive edge queries. We determine (up to logarithmic factors) the number of queries necessary both for detecting the presence of a planted clique and for finding the planted clique. Specifically, let $$G \sim G(n,1/2,k)$$ be a random graph on $$n$$ vertices with a planted clique of size $$k$$. We show that no algorithm that makes at most $q = o(n^2 / k^2 + n)$ adaptive queries to the adjacency matrix of $$G$$ is likely to find the planted clique. On the other hand, when $$k \geq (2+\epsilon) \log_2 n$$ there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making $$q = O( (n^2 / k^2) \log^2 n + n \log n)$$ adaptive queries. For detection, the additive $$n$$ term is not necessary: the number of queries needed to detect the presence of a planted clique is $n^2 / k^2$ (up to logarithmic factors). 

   more » « less
2. The Stochastic Block Model Has the Overlap Graph Property for Modularity

   https://doi.org/10.4230/lipics.icalp.2026.28  

   Bhamidi, Shankar; Gamarnik, David; van_der_Hofstad, Remco; Litvak, Nelly; Prałat, Paweł; Skerman, Fiona; Tousinejad, Yasmin (January 2026, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bhattacharya, Sayan; Nanongkai, Danupon; Benedikt, Michael; Puppis, Gabriele (Ed.)

   Abstract: The overlap gap property (OGP) is a statement about the geometry of near-optimal solutions. Exhibiting OGP implies failure of a class of local algorithms; and has been observed to coincide with conjectured algorithmic limits in problems with statistical computational gap. We consider the Stochastic Block Model (SBM), where the graph has a planted partition with k equal-size blocks which form the "communities", and where, for parameters p > q, vertices within the same community connect with probability p, while vertices in different communities connect with probability q, independently across pairs of vertices. Modularity-based clustering algorithms have become ubiquitous in applications. This article studies theoretical limits of local algorithms based on the modularity score on the SBM. We establish that modularity exhibits OGP on the SBM. This rules out a class of local algorithms based on modularity for recovery in the SBM, and shows slow mixing time for a related Markov Chain. Theoretically this is one of the few instances where OGP has been established for a "planted" model, as most such analyses to date consider the "null" model. As part of our analysis, we extend a result by Bickel and Chen 2009, who established that with high probability, the modularity optimal partition of SBM is o(n) local moves away from the planted partition, where n is the graph size. We show that, with high probability, any partition with modularity score sufficiently near the optimal value is close to the planted partition. 

   more » « less
3. Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity

   https://doi.org/10.4230/lipics.icalp.2025.20  

   Bansal, Ishan; Cheriyan, Joe; Khanna, Sanjeev; Simmons, Miles (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Censor-Hillel, Keren; Grandoni, Fabrizio; Ouaknine, Joel; Puppis, Gabriele (Ed.)

   Abstract: We present improved approximation algorithms for some problems in the related areas of Capacitated Network Design and Flexible Graph Connectivity. In the Cap-k-ECSS problem, we are given a graph G = (V,E) whose edges have non-negative costs and positive integer capacities, and the goal is to find a minimum-cost edge-set F such that every non-trivial cut of the graph G' = (V,F) has capacity at least k. Let n = |V| and let u_{min} (respectively, u_{max}) denote the minimum (respectively, maximum) capacity of an edge; assume that u_{max} ≤ k. We present an O(log({k}/u_{min}))-approximation algorithm for the Cap-k-ECSS problem, asymptotically improving upon the previous best approximation ratio of min(O(log{n}), k, 2u_{max}, 6 ⋅ {⌈ k/u_{min} ⌉}) whenever log(k/u_{min}) = o(log{n}) and u_{max} is sufficiently large. In the (p,q)-Flexible Graph Connectivity problem, denoted (p,q)-FGC, the input is a graph G = (V, E) where E is partitioned into safe and unsafe edges, and the goal is to find a minimum-cost edge-set F such that the subgraph G' = (V, F) remains p-edge connected upon removal of any q unsafe edges from F. We present an 8-approximation algorithm for the (1,q)-FGC problem that improves upon the previous best approximation ratio of (q+1). Both of our results are obtained by using natural LP relaxations strengthened with the knapsack-cover inequalities, and then, during the rounding process, utilizing a recent O(1)-approximation algorithm for the Cover Small Cuts problem. In the latter problem, the goal is to find a minimum-cost set of links such that each non-trivial cut of capacity less than a specified value is covered by a link. We also show that the problem of covering small cuts inherently arises in another variant of (p,q)-FGC. Specifically, we give Cook reductions that preserve approximation ratios within O(1) factors between the (2,q)-FGC problem and the 2-Cover Small Cuts problem; in the latter problem, each small cut needs to be covered by two links. 

   more » « less
4. A Faster Algorithm for Minimum-cost Bipartite Perfect Matching in Planar Graphs

   https://doi.org/10.1145/3365006  

   Asathulla, Mudabir Kabir; Khanna, Sanjeev; Lahn, Nathaniel; Raghvendra, Sharath (January 2020, ACM Transactions on Algorithms)

   null (Ed.)

   Given a weighted planar bipartite graph G ( A ∪ B , E ) where each edge has an integer edge cost, we give an Õ( n 4/3 log nC ) time algorithm to compute minimum-cost perfect matching; here C is the maximum edge cost in the graph. The previous best-known planarity exploiting algorithm has a running time of O ( n 3/2 log n ) and is achieved by using planar separators (Lipton and Tarjan ’80). Our algorithm is based on the bit-scaling paradigm (Gabow and Tarjan ’89). For each scale, our algorithm first executes O ( n 1/3 ) iterations of Gabow and Tarjan’s algorithm in O ( n 4/3 ) time leaving only O ( n 2/3 ) vertices unmatched. Next, it constructs a compressed residual graph H with O ( n 2/3 ) vertices and O ( n ) edges. This is achieved by using an r -division of the planar graph G with r = n 2/3 . For each partition of the r -division, there is an edge between two vertices of H if and only if they are connected by a directed path inside the partition. Using existing efficient shortest-path data structures, the remaining O ( n 2/3 ) vertices are matched by iteratively computing a minimum-cost augmenting path, each taking Õ( n 2/3 ) time. Augmentation changes the residual graph, so the algorithm updates the compressed representation for each partition affected by the change in Õ( n 2/3 ) time. We bound the total number of affected partitions over all the augmenting paths by O ( n 2/3 log n ). Therefore, the total time taken by the algorithm is Õ( n 4/3 ). 

   more » « less
5. Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism

   https://doi.org/10.4230/lipics.esa.2025.91  

   Dhulipala, Laxman; Henzinger, Monika; Li, George Z; Liu, Quanquan C; Sricharan, A R; Zhu, Leqi (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (33rd Annual European Symposium on Algorithms, ESA 2025))

   Benoit, Anne; Kaplan, Haim; Wild, Sebastian; Herman, Grzegorz (Ed.)

   Abstract: Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the k-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of n due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. When applied to vectors with n dimensions, we solve a number of important graph problems with better bounds than previous work. Specifically, we apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including k-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge differentially private (LEDP) algorithm for k-core decomposition that results in an approximation with O(ε^{-1} log n) additive error and no multiplicative error in O(n) rounds. We also give a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in O(log² n) rounds for any constant η > 0. Both of these results are asymptotically tight against our new lower bound of Ω(log n) for any constant-factor approximation algorithm for k-core decomposition. Our new algorithms for k-core decomposition also directly lead to new algorithms for the related problems of densest subgraph and low out-degree ordering. Finally, we give novel LEDP differentially private defective coloring algorithms that use number of colors given in terms of the arboricity of the graph. 

   more » « less