Maximum Matching via Maximal Matching Queries
Abstract
We study approximation algorithms for Maximum Matching that are given access to the input graph solely via an edgequery maximal matching oracle. More specifically, in each round, an algorithm queries a set of potential edges and the oracle returns a maximal matching in the subgraph spanned by the query edges that are also contained in the input graph. This model is more general than the vertexquery model introduced by Binti Khalil and Konrad [FSTTCS’20], where each query consists of a subset of vertices and the oracle returns a maximal matching in the subgraph of the input graph induced by the queried vertices.
In this paper, we give tight bounds for deterministic edgequery algorithms for up to three rounds. In more detail:

As our main result, we give a deterministic $3$round edgequery algorithm with approximation factor $0.625$ on bipartite graphs. This result establishes a separation between the edgequery and the vertexquery models since every deterministic 3round vertexquery algorithm has an approximation factor of at most $0.6$ [Binti Khalil, Konrad, FSTTCS’20], even on bipartite graphs. Our algorithm can also be implemented in the semistreaming model of computation in a straightforward manner and improves upon the stateoftheart $3$pass $0.6111$approximation algorithm by Feldman and Szarf [APPROX’22] for bipartite graphs.

We show that the aforementioned algorithm is optimal in that every deterministic $3$round edgequery algorithm has an approximation factor of at most $0.625$, even on bipartite graphs.

Last, we also give optimal bounds for one and two query rounds, where the best approximation factors achievable are $1/2$ and $1/2 + \Theta(\frac{1}{n})$, respectively, where $n$ is the number of vertices in the input graph.
2023 © Kheeran K. Naidu