Matching in Stochastically Evolving Graphs

Eleni C. Akrida, Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis, Viktor ZamaraevarXiv 2020 · arXiv

Introduction

Matching problems are a cornerstone of algorithmic research, with applications ranging from organ donation networks to real-time advertising auctions. Traditionally, these problems are analyzed in either a static setting or a purely online setting. However, many practical scenarios involve "stochastic evolution," where we have partial information about the future. This paper explores the Maximum Cardinality Matching problem in Stochastically Evolving Graphs, introducing a framework where vertex arrivals are known but departures are unpredictable.

The Stochastic Arrival-Departure Model

In the proposed model, every vertex $v$ in a graph $G$ has a known arrival day and a "deadline" day. While the arrival is deterministic, the vertex may depart (or "die") at any point between arrival and deadline according to a known probability distribution.

Figure 1: A graph instance illustrating vertex arrival and departure intervals.

This setup creates a fundamental "Wait or Act" dilemma. An algorithm must decide whether to match an available pair immediately or wait for a potentially better match to arrive. Waiting carries the risk that one of the current vertices will depart, rendering the match impossible. The paper formalizes the intuition that a vertex's departure is just as critical a trigger for algorithmic action as its arrival.

The Price of Stochasticity

To quantify the impact of uncertainty, the authors define the Price of Stochasticity. This metric is the ratio between the expected matching size achieved by an optimal adaptive algorithm (which makes decisions based on the current state of the graph) and the "hindsight optimum"—the maximum matching found by an algorithm with perfect knowledge of all future departure times.

Figure 4: Decomposition of a graph G into various sub-instances used to demonstrate the upper bounds of the model.

The most significant theoretical result is that the price of stochasticity is at most $2/3$. By constructing specific graph instances (such as the one shown in Figure 4), the authors demonstrate that as the number of vertices $n$ approaches infinity, even the most sophisticated adaptive algorithm cannot guarantee matching more than $2/3$ of the edges that a hindsight-optimal algorithm would identify. This represents a fundamental limit on efficiency imposed by stochasticity.

Algorithmic Contributions

The research provides several key tools for navigating these uncertain graphs:

  • FPRAS (Fully Polynomial Randomized Approximation Scheme): The authors developed a specialized randomized algorithm to efficiently estimate the expected size of a maximum matching. This is crucial because calculating the exact value is computationally intensive.
  • Deterministic Equivalence: A surprising proof shows that for any stochastic graph, there exists a deterministic adaptive algorithm that is just as effective as any randomized one, simplifying the search for optimal strategies.
  • Two-Step Optimality: While the general problem is complex, the authors provide a polynomial-time optimal solution for graphs that evolve over exactly two timesteps, utilizing a "Split-Matching Algorithm."

Conclusion and Future Directions

This paper establishes a rigorous framework for matching in dynamic, uncertain environments. While the $2/3$ bound provides a clear theoretical ceiling, the computational complexity for models with more than two timesteps ($T > 2$) remains an open question. The authors conjecture that their approach remains optimal for larger $T$, but formal proofs are needed. Additionally, future work could explore alternative objective functions, such as minimizing the maximum regret across all possible departure scenarios.

Summary updated

Abstract

This paper studies the maximum cardinality matching problem in stochastically evolving graphs. We formally define the arrival-departure model with stochastic departures. There, a graph is sampled from a specific probability distribution and it is revealed as a series of snapshots. Our goal is to study algorithms that create a large matching in the sampled graphs. We define the price of stochasticity for this problem which intuitively captures the loss of any algorithm in the worst case in the size of the matching due to the uncertainty of the model. Furthermore, we prove the existence of a deterministic optimal algorithm for the problem. In our second set of results we show that we can efficiently approximate the expected size of a maximum cardinality matching by deriving a fully randomized approximation scheme (FPRAS) for it. The FPRAS is the backbone of a probabilistic algorithm that is optimal when the model is defined over two timesteps. Our last result is an upper bound of $\frac{2}{3}$ on the price of stochasticity. This means that there is no algorithm that can match more than $\frac{2}{3}$ of the edges of an optimal matching in hindsight.
BibTeX
@misc{akrida2020matching,
  author = {Eleni C. Akrida and Argyrios Deligkas and George B. Mertzios and Paul G. Spirakis and Viktor Zamaraev},
  title = {{Matching in Stochastically Evolving Graphs}},
  year = {2020},
  eprint = {2005.08263},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.08263},
}
Figure