More Like this

1. Stochastic Matching via In-n-Out Local Computation Algorithms

   Azarmehr, Amir; Behnezhad, Soheil; Ghafari, Alma; Rubinfeld, Ronitt (June 2025, 57th Annual ACM Symposium on Theory of Computing (STOC 2025))

   Consider the following stochastic matching problem. We are given a known graph 𝐺 = (𝑉 , 𝐸). An unknown subgraph 𝐺𝑝 = (𝑉 , 𝐸𝑝 ) is realized where 𝐸𝑝 includes every edge of 𝐸 independently with some probability 𝑝 ∈ (0, 1]. The goal is to query a sparse subgraph 𝐻 of 𝐺, such that the realized edges in 𝐻 include an approximate maximum matching of 𝐺𝑝 . This problem has been studied extensively over the last decade due to its applications in kidney exchange, online dating, and online labor markets. For any fixed 𝜀 > 0, [BDH STOC’20] showed that any graph 𝐺 has a subgraph 𝐻 with quasipoly(1/𝑝) = (1/𝑝)poly(log(1/𝑝 ) ) maximum degree, achieving a (1 − 𝜀)-approximation. A major open question is the best approximation achievable with poly(1/𝑝)- degree subgraphs. A long line of work has progressively improved the approximation in the poly(1/𝑝)-degree regime from .5 [BDH+ EC’15] to .501 [AKL EC’17], .656 [BHFR SODA’19], .666 [AB SOSA’19], .731 [BBD SODA’22] (bipartite graphs), and most recently to .68 [DS ’24]. In this work, we show that a poly(1/𝑝)-degree subgraph can obtain a (1 − 𝜀)-approximation for any desirably small fixed 𝜀 > 0, achieving the best of both worlds. Beyond its quantitative improvement, a key conceptual contribu- tion of our work is to connect local computation algorithms (LCAs) to the stochastic matching problem for the first time. While prior work on LCAs mainly focuses on their out-queries (the number of vertices probed to produce the output of a given vertex), our analysis also bounds the in-queries (the number of vertices that probe a given vertex). We prove that the outputs of LCAs with bounded in- and out-queries (in-n-out LCAs for short) have limited correlation, a property that our analysis crucially relies on and might find applications beyond stochastic matchings. 

   more » « less
2. Query Complexity of Stochastic Minimum Vertex Cover

   https://doi.org/10.4230/LIPIcs.ITCS.2025.41  

   Derakhshan, Mahsa; Saneian, Mohammad; Xun, Zhiyang (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   We study the stochastic minimum vertex cover problem for general graphs. In this problem, we are given a graph G=(V, E) and an existence probability p_e for each edge e ∈ E. Edges of G are realized (or exist) independently with these probabilities, forming the realized subgraph H. The existence of an edge in H can only be verified using edge queries. The goal of this problem is to find a near-optimal vertex cover of H using a small number of queries. Previous work by Derakhshan, Durvasula, and Haghtalab [STOC 2023] established the existence of 1.5 + ε approximation algorithms for this problem with O(n/ε) queries. They also show that, under mild correlation among edge realizations, beating this approximation ratio requires querying a subgraph of size Ω(n ⋅ RS(n)). Here, RS(n) refers to Ruzsa-Szemerédi Graphs and represents the largest number of induced edge-disjoint matchings of size Θ(n) in an n-vertex graph. In this work, we design a simple algorithm for finding a (1 + ε) approximate vertex cover by querying a subgraph of size O(n ⋅ RS(n)) for any absolute constant ε > 0. Our algorithm can tolerate up to O(n ⋅ RS(n)) correlated edges, hence effectively completing our understanding of the problem under mild correlation. 

   more » « less
3. Stochastic Minimum Vertex Cover in General Graphs: A 3/2-Approximation

   https://doi.org/10.1145/3564246.3585230  

   Derakhshan, Mahsa; Durvasula, Naveen; Haghtalab, Nika (June 2023, ACM)

   We study the stochastic vertex cover problem. In this problem, G = (V, E) is an arbitrary known graph, and G⋆ is an unknown random subgraph of G where each edge e is realized independently with probability p. Edges of G⋆ can only be verified using edge queries. The goal in this problem is to find a minimum vertex cover of G⋆ using a small number of queries. Our main result is designing an algorithm that returns a vertex cover of G⋆ with size at most (3/2+є) times the expected size of the minimum vertex cover, using only O(n/є p) non-adaptive queries. This improves over the best-known 2-approximation algorithm by Behnezhad, Blum and Derakhshan [SODA’22] who also show that Ω(n/p) queries are necessary to achieve any constant approximation. Our guarantees also extend to instances where edge realizations are not fully independent. We complement this upperbound with a tight 3/2-approximation lower bound for stochastic graphs whose edges realizations demonstrate mild correlations. 

   more » « less
4. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs

   https://doi.org/10.1137/1.9781611975994.139  

   Chudnovsky, Maria.; Pillipczuk, Marcin.; Pillipczuk, Mihal; and Thomasse, Stephan. (April 2020, Proceedings of the annual ACMSIAM symposium on discrete algorithms)

   In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In H-free graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter ε > 0, finds an independent set in G of cardinality within a factor of (1 – ε) of the optimum in time exponential in a polynomial of log | V(G) | and ε−1. That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set. 

   more » « less
5. (Optimal) Online Bipartite Matching with Degree Information

   Aamand, Anders; Chen, Justin Y; Indyk, Piotr (January 2022, Conference on Neural Information Processing Systems)

   We propose a model for online graph problems where algorithms are given access to an oracle that predicts (e.g., based on modeling assumptions or on past data) the degrees of nodes in the graph. Within this model, we study the classic problem of online bipartite matching, and a natural greedy matching algorithm called MinPredictedDegree, which uses predictions of the degrees of offline nodes. For the bipartite version of a stochastic graph model due to Chung, Lu, and Vu where the expected values of the offline degrees are known and used as predictions, we show that MinPredictedDegree stochastically dominates any other online algorithm, i.e., it is optimal for graphs drawn from this model. Since the “symmetric” version of the model, where all online nodes are identical, is a special case of the well-studied “known i.i.d. model”, it follows that the competitive ratio of MinPredictedDegree on such inputs is at least 0.7299. For the special case of graphs with power law degree distributions, we show that MinPredictedDegree frequently produces matchings almost as large as the true maximum matching on such graphs. We complement these results with an extensive empirical evaluation showing that MinPredictedDegree compares favorably to state-of-the-art online algorithms for online matching. 

   more » « less