DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.116

A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time

Authors: Sepideh Mahabadi, Mohammad Roghani, and Jakub Tarnawski

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We study the problem of estimating the size of a maximum matching in sublinear time. The problem has been studied extensively in the literature and various algorithms and lower bounds are known for it. Our result is a 0.5109-approximation algorithm with a running time of Õ(n√n). All previous algorithms either provide only a marginal improvement (e.g., 2^{-280}) over the 0.5-approximation that arises from estimating a maximal matching, or have a running time that is nearly n². Our approach is also arguably much simpler than other algorithms beating 0.5-approximation.

Cite as

Sepideh Mahabadi, Mohammad Roghani, and Jakub Tarnawski. A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 116:1-116:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mahabadi_et_al:LIPIcs.ICALP.2025.116,
  author =	{Mahabadi, Sepideh and Roghani, Mohammad and Tarnawski, Jakub},
  title =	{{A 0.51-Approximation of Maximum Matching in Sublinear n^\{1.5\} Time}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{116:1--116:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.116},
  URN =		{urn:nbn:de:0030-drops-234932},
  doi =		{10.4230/LIPIcs.ICALP.2025.116},
  annote =	{Keywords: Sublinear Algorithms, Maximum Matching, Maximal Matching, Approximation Algorithm}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2025.74

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover

Authors: Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

We study the metric Steiner tree problem in the sublinear query model. In this problem, for a set of n points V in a metric space given to us by means of query access to an n× n matrix w, and a set of terminals T ⊆ V, the goal is to find the minimum-weight subset of the edges that connects all the terminal vertices. Recently, Chen, Khanna and Tan [SODA'23] gave an algorithm that uses Õ(n^{13/7}) queries and outputs a (2-η)-estimate of the metric Steiner tree weight, where η > 0 is a universal constant. A key component in their algorithm is a sublinear algorithm for a particular set cover problem where, given a set system (𝒰, ℱ), the goal is to provide a multiplicative-additive estimate for |𝒰|-SC(𝒰, ℱ). Here 𝒰 is the set of elements, ℱ is the collection of sets, and SC(𝒰, ℱ) denotes the optimal set cover size of (𝒰, ℱ). In particular, their algorithm returns a (1/4, ε⋅|𝒰|)-multiplicative-additive estimate for this set cover problem using Õ(|ℱ|^{7/4}) membership oracle queries (querying whether a set S ∈ 𝒮 contains an element e ∈ 𝒰), where ε is a fixed constant. In this work, we improve the query complexity of (2-η)-estimating the metric Steiner tree weight to Õ(n^{5/3}) by showing a (1/2, ε⋅|𝒰|)-estimate for the above set cover problem using Õ(|ℱ|^{5/3}) membership queries. To design our set cover algorithm, we estimate the size of a random greedy maximal matching for an auxiliary multigraph that the algorithm constructs implicitly, without access to its adjacency list or matrix. Previous analyses of random greedy maximal matching have focused on simple graphs, assuming access to their adjacency list or matrix. To address this, we extend the analysis of Behnezhad [FOCS'21] of random greedy maximal matching on simple graphs to multigraphs, and prove additional properties that may be of independent interest.

Cite as

Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian. Sublinear Metric Steiner Tree via Improved Bounds for Set Cover. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 74:1-74:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mahabadi_et_al:LIPIcs.ITCS.2025.74,
  author =	{Mahabadi, Sepideh and Roghani, Mohammad and Tarnawski, Jakub and Vakilian, Ali},
  title =	{{Sublinear Metric Steiner Tree via Improved Bounds for Set Cover}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{74:1--74:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.74},
  URN =		{urn:nbn:de:0030-drops-227029},
  doi =		{10.4230/LIPIcs.ITCS.2025.74},
  annote =	{Keywords: Sublinear Algorithms, Steiner Tree, Set Cover, Maximum Matching, Approximation Algorithm}
}

Search Results

Documents authored by Tarnawski, Jakub

A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time

Abstract

Cite as

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover

Abstract

Cite as

Thanks for your feedback!

Could not send message