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 languageEnglish
Title of host publication40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
EditorsPetra Berenbrink, Patricia Bouyer, Anuj Dawar, Mamadou Moustapha Kanté
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages41:1-41:22
Volume254
ISBN (Electronic)9783959772662
DOIs
Publication statusPublished - 3 Mar 2023
Event40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
- Universität Hamburg, Hamburg, Germany
Duration: 7 Mar 20239 Mar 2023
https://www.conferences.uni-hamburg.de/event/272/

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume254
ISSN (Print)1868-8969

Conference

Conference40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Country/TerritoryGermany
CityHamburg
Period7/03/239/03/23
Internet address

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.

Publisher Copyright:
© Christian Konrad, Kheeran K. Naidu, and Arun Steward.

Fingerprint

Dive into the research topics of 'Maximum Matching via Maximal Matching Queries'. Together they form a unique fingerprint.

Cite this