# Maximum Matching via Maximal Matching Queries

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

3 Citations (Scopus)

## Abstract

We study approximation algorithms for Maximum Matching that are given access to the input graph solely via an edge-query 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 vertex-query 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 edge-query algorithms for up to three rounds. In more detail:
1) As our main result, we give a deterministic 3-round edge-query algorithm with approximation factor 0.625 on bipartite graphs. This result establishes a separation between the edge-query and the vertex-query models since every deterministic 3-round vertex-query 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 semi-streaming model of computation in a straightforward manner and improves upon the state-of-the-art 3-pass 0.6111-approximation algorithm by Feldman and Szarf [APPROX'22] for bipartite graphs.
2) We show that the aforementioned algorithm is optimal in that every deterministic 3-round edge-query algorithm has an approximation factor of at most 0.625, even on bipartite graphs.
3) Last, we also give optimal bounds for one and two query rounds, where the best approximation factors achievable are 1/2 and 1/2 + Θ(1/n), respectively, where n is the number of vertices in the input graph.
Original language English 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 Petra Berenbrink, Patricia Bouyer, Anuj Dawar, Mamadou Moustapha Kanté Schloss Dagstuhl - Leibniz-Zentrum für Informatik 41:1-41:22 254 9783959772662 https://doi.org/10.4230/LIPIcs.STACS.2023.41 Published - 3 Mar 2023 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) - Universität Hamburg, Hamburg, GermanyDuration: 7 Mar 2023 → 9 Mar 2023https://www.conferences.uni-hamburg.de/event/272/

### Publication series

Name Leibniz International Proceedings in Informatics, LIPIcs 254 1868-8969

### Conference

Conference 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) Germany Hamburg 7/03/23 → 9/03/23 https://www.conferences.uni-hamburg.de/event/272/

### Bibliographical note

Funding Information:
Funding C.K. is supported by EPSRC New Investigator Award EP/V010611/1. K.K.N. is supported by EPSRC DTP studentship EP/T517872/1.