Stochastic Matching Under Per Vertex Query Constraints

25 concepts17 papers1 proposal

Imagine managing a large-scale kidney exchange network. Nodes represent patient-donor pairs, and edges represent potential medical compatibility. On paper, many matches look viable. In reality, an edge only exists with some probability $p$, and confirming its viability requires an expensive, time-consuming crossmatch test.

Because medical resources are limited, we cannot test every single potential pair. Crucially, each patient or hospital can only tolerate a small, fixed number of tests. This imposes a per-vertex query constraint: we must select a sparse subgraph to verify, ensuring no vertex exceeds its strict budget of queries, such that the actual realized edges within this subgraph contain a near-optimal global matching.

The core challenge of this research direction is finding high-quality solutions in uncertain graphs while strictly limiting the number of queries allowed per participant.

The Core Tension: Ignorance vs. Omniscience

The gold standard for any stochastic optimization problem is the omniscient baseline—the maximum matching an observer could find if they knew the outcome of every single potential edge in advance.

If we have a graph with $n$ vertices, a naive approach might suggest we need a number of queries that scales with $n$ to find a good matching. However, a foundational line of work initiated by Blum et al. (2014) and Procaccia et al. (2015) proved a remarkable counterintuitive fact: ignorance is almost bliss. We can achieve a $(1-\epsilon)$ fraction of the omniscient maximum matching by querying only a constant number of edges per vertex, completely independent of the total network size $n$.

This means that large-scale resource allocation systems can remain highly effective without exhaustive testing. The query overhead required to find a near-optimal matching depends only on the desired precision $\epsilon$ and the edge probability $p$, not on how massive the network becomes.

Why It Works: The Power of Constant-Degree Subgraphs

How can a local, bounded-degree exploration capture a global optimum? The intuition lies in the structural properties of matchings in random subgraphs. If we select a subgraph where every vertex has a small degree, and then reveal which edges are active, why doesn't the matching collapse?

Initially, Bansal et al. (2012) tackled this via Linear Programming (LP) relaxations. They showed that by solving a fractional matching problem on the expected graph and carefully rounding the solution, one can select a subset of edges to probe that respects per-vertex limits while guaranteeing a strong approximation of the optimal weighted matching.

To push this to a near-optimal $(1-\epsilon)$ approximation, the authors of Behnezhad et al. (2020) bypassed long-standing structural barriers (such as the Ruzsa-Szemerédi barrier) by introducing a "vertex-independent matching" technique. Instead of letting queries at one vertex heavily dictate choices at another, they constructed a queried subgraph with a maximum degree independent of the graph's size. This ensures that even when edges fail randomly, the remaining active edges are distributed densely enough across the network to support a massive, globally coordinated matching.

Adaptive vs. Non-Adaptive Strategies

Algorithms in this domain generally fall into two categories:

  1. Adaptive algorithms, where the choice of which edge to query next depends on the outcomes (success or failure) of previous queries.
  2. Non-adaptive algorithms, where the algorithm must select the entire subgraph of edges to test upfront, before knowing which ones actually exist.

Non-adaptive algorithms are highly desirable in practice because all tests can be run simultaneously in parallel. However, they are theoretically harder because the algorithm cannot pivot if a critical edge fails.

Despite this difficulty, significant breakthroughs have been achieved. The authors of Assadi et al. (2017) broke the natural $0.5$ approximation barrier for non-adaptive algorithms using a structural result known as the $b$-matching lemma, proving that a non-adaptive strategy can guarantee a matching size of at least 52% of the optimum. This was further extended to weighted graphs by Reyhani (2017) and Behnezhad et al. (2018), demonstrating that simple, non-adaptive probing strategies can effectively prioritize which potential matches are most likely to contribute to the global optimum. More recently, Saneian et al. (2025) achieved optimal query complexity for the weighted setting, balancing the trade-off between edge verification costs and matching value.

Beyond Matching: Stochastic Vertex Covers

The insight that a few queries per vertex suffice for stochastic optimization extends to other fundamental graph problems, such as the Stochastic Minimum Vertex Cover (MVC) problem. Here, the goal is to find a small set of vertices that covers all realized edges in an uncertain graph.

The authors of Behnezhad et al. (2021) demonstrated that a $(2+\epsilon)$-approximation for the minimum vertex cover can be achieved using a constant number of queries per vertex relative to $p$. This bound matches the best-known approximation ratio for deterministic graphs under standard complexity assumptions. This was later improved by Derakhshan et al. (2023) to a $3/2$-approximation, establishing that a query complexity of $O(n/p)$ is asymptotically optimal for finding vertex covers in uncertain environments.

Connection to Sublinear Graph Analysis

This paradigm shares a deep mathematical connection with sublinear-time graph algorithms and property testing, where the goal is to analyze a massive network while looking at a minuscule fraction of it.

For instance, sampling an edge uniformly from an unknown graph traditionally required extensive exploration. However, Rosenbaum (2017) and later Eden et al. (2022) proved that exact uniform edge sampling can be achieved in $O(n/\sqrt{m})$ time using basic vertex and neighbor queries, matching the theoretical lower bound. Similar optimal query boundaries appear when testing graph arboricity (Eden et al. (2017)), counting triangles (Assadi et al. (2022)), or using quantum speedups to sample random spanning trees (Apers et al. (2025)).

Whether dealing with stochastic edge uncertainty or massive graph scales, the underlying lesson remains the same: carefully chosen, query-constrained local views are powerful enough to reveal or preserve global properties.

Key Foundational Work

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. (2012) — contributed 3 concept elements to this direction.
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_limited_edge_verification_2241e4ac,
  title = {limited edge verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/limited-edge-verification/rdr_2241e4acea4a46c584a73df2477b91d1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_limited_edge_verification_2241e4ac_v1,
  title = {limited edge verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/limited-edge-verification/rdr_2241e4acea4a46c584a73df2477b91d1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake