The Stochastic Matching Problem with (Very) Few Queries

Abstract

Motivated by an application in kidney exchange, we study the following stochastic matching problem: we are given a graph G(V,E) (not necessarily bipartite), where each edge in E is realized with some constant probability p > 0 and the goal is to find a maximum matching in the realized graph. An algorithm in this setting is allowed to make queries to edges in E in order to determine whether or not they are realized.