PaperlayerView exact revision on arXiv

Source-linked AI summary

Maximum Matching in Semi-Streaming with Few Passes

Christian Konrad, Frédéric Magniez, Claire Mathieu

arXiv:1112.0184v3cs.DS

TL;DR

Semi-streaming matching asks whether an algorithm using limited memory and few passes can outperform Greedy’s 1/2 approximation. The paper develops Greedy-based algorithms for one and two passes, with random arrival needed for the one-pass guarantees but not the two-pass guarantees. Its algorithms exceed 1/2 for bipartite and general graphs.

  • Problem

    Whether semi-streaming matching can beat Greedy’s 1/2 approximation has remained open, while prior multipass algorithms cited for gains over 1/2 require at least three passes.

    Source: §1 · p. 2

  • Method

    The algorithms repeatedly apply Greedy on carefully chosen subgraphs, with deterministic two-pass variants also using subroutines that select edge subsets.

    Source: §1 · p. 3

  • Results

    One-pass expected approximation is 1/2 + 0.005 for bipartite graphs and 1/2 + 0.003 for general graphs under uniform random order; two-pass bipartite algorithms achieve 1/2 + 0.019 for arbitrary order.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The paper establishes semi-streaming matching guarantees strictly above 1/2 with one or two passes, with arbitrary-order guarantees in two passes.

    Source: §1 · p. 3

    The model assumes constant-time stream reads and O(t(n)) preprocessing and postprocessing.

    Source: §2 · p. 5

Abstract

from arXiv · show

In the semi-streaming model, an algorithm receives a stream of edges of a graph in arbitrary order and uses a memory of size $O(n \mbox{ polylog } n)$, where $n$ is the number of vertices of a graph. In this work, we present semi-streaming algorithms that perform one or two passes over the input stream for maximum matching with no restrictions on the input graph, and for the important special case of bipartite graphs that we refer to as maximum bipartite matching (MBM). The Greedy matching algorithm performs one pass over the input and outputs a $1/2$ approximation. Whether there is a better one-pass algorithm has been an open question since the appearance of the first paper on streaming algorithms for matching problems in 2005 [Feigenbaum et al., SODA 2005]. We make the following progress on this problem: In the one-pass setting, we show that there is a deterministic semi-streaming algorithm for MBM with expected approximation factor $1/2+0.005$, assuming that edges arrive one by one in (uniform) random order. We extend this algorithm to general graphs, and we obtain a $1/2+0.003$ approximation. In the two-pass setting, we do not require the random arrival order assumption (the edge stream is in arbitrary order). We present a simple randomized two-pass semi-streaming algorithm for MBM with expected approximation factor $1/2 + 0.019$. Furthermore, we discuss a more involved deterministic two-pass semi-streaming algorithm for MBM with approximation factor $1/2 + 0.019$ and a generalization of this algorithm to general graphs with approximation factor $1/2 + 0.0071$.

1 Introduction

The paper asks whether semi-streaming matching can beat Greedy’s 1/2 approximation with only one or two passes. It presents algorithms that exceed 1/2 for bipartite and general graphs, using random arrival for one pass but not two.

1 Introduction

  • One pass gives bipartite matching an expected 1/2 + 0.005 approximation and general matching a 1/2 + 0.003 approximation under uniform random edge order; two-pass bipartite algorithms attain 1/2 + 0.019 without that assumption, while the deterministic general-graph extension attains 1/2 + 0.0071.The randomized two-pass bipartite algorithm also attains expected 1/2 + 0.019 for any arrival order.Source: §1 · p. 3
  • All algorithms build on Greedy-based matching and simulate three passes that find length-2 and length-3 augmenting paths using fewer passes.The deterministic two-pass algorithms also use subroutines to compute particular edge subsets.Source: §1 · p. 3
  • If full-stream Greedy is no better than 1/2 + ϵ, then after one third of the edges it already gives a 1/2 − ϵ approximation and is close to maximal.The one-pass algorithm divides arrivals into three phases to construct M0, M1, and M2; random order makes each phase’s edge subset random.Source: §1 · pp. 3–4
  • For arbitrary arrival order, the randomized two-pass method builds a greedy matching on a small random subset of A, then uses a second pass to complete 3-augmenting paths.In a bipartite graph with a perfect matching, the restricted greedy matching is near-perfect on that subset regardless of arrival order.Source: §1 · p. 4
  • The deterministic arbitrary-order two-pass method replaces the first-pass subset matching with an incomplete semi-matching that limits degrees on B, then finds 3-augmenting paths in the second pass.The semi-matching is built by greedily adding edges whose A endpoint is unused and whose B endpoint has degree below λ.Source: §1 · p. 4
  • For general graphs, the extensions address bad triangles that can block augmenting paths: uniform random order limits their frequency for one pass, while a combinatorial argument bounds them for deterministic two-pass algorithms.Unlike the approach cited in the paper, the one-pass extension does not require repeatedly sampling bipartite graphs.Source: §1 · p. 4

2 Preliminaries

The preliminaries define the matching concepts, graph notation, and semi-streaming model used by the algorithms. They also specify approximation under randomness and explain why Greedy provides a 1/2 baseline.

2 Preliminaries

  • A matching uses at most one edge per vertex; maximum means largest cardinality, while maximal means no additional edge can be added.MBM denotes maximum matching in a bipartite graph, and MM denotes maximum matching in a general graph.Source: §2 · pp. 4–5
  • An augmenting path alternates between edges outside and inside a matching, begins and ends at unmatched vertices, and can increase matching size by one when flipped.The path length is odd and at least three.Source: §2 · p. 5
  • A p(n)-pass semi-streaming algorithm uses at most p(n) passes and O(n polylog n) memory, with O(t(n)) time between reads and for preprocessing and postprocessing.The model assumes each stream read takes constant time.Source: §2 · p. 5
  • A c-approximation outputs a matching at least c times optimum; expectations may be over algorithm coins or arrival order, while the graph remains worst-case.Greedy runs in one pass with O(1) update time and achieves 1/2 because its matching is maximal.Source: §2 · p. 5

3 Three-pass Semi-Streaming Algorithm for Bipartite Graphs on Adversarial Order

The three-pass bipartite algorithm starts with a greedy maximal matching, then searches for length-3 augmenting paths to improve it. When the initial matching is near 1/2 of optimal, many of its edges are 3-augmentable.

3 Three-pass Semi-Streaming Algorithm for Bipartite Graphs on Adversarial Order

  • At least (1/2 − 3ϵ)|M*| edges of a maximal matching are 3-augmentable when its size is at most (1/2 + ϵ)|M*|.A 3-augmentable edge can be replaced by two optimal-matching edges to increase the matching.Source: §3 · p. 6
  • A maximal second-pass matching captures at least half the available 3-augmentable edges, and the third pass uses another maximal matching to complete paths.Figure 3 illustrates this process with a perfect matching of size 13 and two completed augmenting paths.Source: §3 · p. 7, Figure 3 · p. 7
  • The algorithm computes a maximal matching in pass one, finds candidate path edges in pass two, and completes length-3 augmenting paths in pass three.The second and third matchings connect matched vertices to free vertices on alternating sides.Source: §3 · pp. 6–7

4 One-pass Matching Algorithm on Random Order

The paper simulates a three-pass matching strategy in one pass when edges arrive in uniform random order, using greedy matchings on successive stream phases. It proves an expected approximation ratio of 1/2 + 0.005 for bipartite graphs and extends the approach to general graphs with ratio 1/2 + 0.00363.

4 One-pass Matching Algorithm on Random Order

  • The one-pass simulation relies on uniform random arrival: the stream is split into phases so each greedy matching can use a random subset of relevant edges.The paper also extends the one-pass random-order approach from bipartite graphs to general graphs.Source: §4 · p. 7, Algorithm · p. 9, §4.3 · p. 12

4.1 A Lemma on the Convergence of the Greedy Algorithm

  • If greedy is close to a 1/2 approximation in expectation, it builds that matching early in the stream, enabling the one-pass construction.The convergence argument uses a prefix of a uniformly random edge ordering.Source: §4.1 · p. 8

Algorithm

  • For bipartite graphs, the algorithm builds M0, M1, and M2 in three successive stream phases, with M2 completing 3-augmenting paths.It returns the larger of the full-stream greedy matching and the matching augmented from M0.Source: Algorithm · p. 9, Figure 4 · p. 10
  • The deterministic one-pass bipartite algorithm achieves expected approximation ratio 1/2 + 0.005 under uniform random edge order.The analysis selects phase boundaries α = 0.4312 and β = 0.7595.Source: Algorithm · pp. 11–12

4.3 Extension to General Graphs

  • The general-graph extension must account for M1 edges that can block completion of candidate augmenting paths.The analysis bounds the probability that an M0 edge becomes blocked by 1/2, which supports completing many paths with M2.Source: §4.3 · p. 12

Analysis

  • The general-graph analysis bounds the output through the sizes of M0, M1, and M2, accounting for blocked paths and the expected number of 3-augmentable edges.The proof optimizes α and β numerically to obtain the stated approximation ratio.Source: Analysis · pp. 13–14
  • The deterministic one-pass general-graph algorithm achieves expected approximation ratio 1/2 + 0.00363 under uniform random edge order.Its optimized phase boundaries are α = 0.413 and β = 0.708.Source: Analysis · p. 14

5 Randomized Two-pass Algorithm on any Order

The section develops a randomized two-pass algorithm for maximum bipartite matching that works with arbitrary edge arrival order. Its key ingredient is a greedy matching guarantee on a random vertex subset, yielding an expected approximation ratio of 1/2 + 0.019.

5.1 Matching Many Vertices of a Random Vertex Subset

  • For any input stream, greedy matching on edges incident to a random p-sample A′ has expected size at least p/(1 + p) times the full graph’s maximum matching size.This guarantee underpins the two-pass algorithm’s use of a sampled vertex subset.Source: §5.1 · p. 15

5.2 A Randomized Two-pass Algorithm for Bipartite Graphs

  • The algorithm samples A′, builds greedy matchings on the full graph and on edges incident to A′ in its first pass, then uses a second-pass matching to complete augmenting paths.Edges from the sampled matching that form parts of length-2 paths are used to construct the second-pass edge set.Source: §5.2 · p. 16
  • 1/2 + 0.019 expected approximation ratio for maximum bipartite matching, for any graph and arrival order, using two passes.The guarantee is over the algorithm’s internal random coin flips.Source: §5.2 · p. 17

6 Deterministic Two-pass Algorithm on any Order

This section develops deterministic two-pass semi-streaming algorithms for bipartite and general-graph matching under arbitrary edge arrival order. Both combine Greedy with additional edge structures in the first pass, then use the second pass to complete augmenting paths.

6.1 Bipartite Graphs

  • For bipartite graphs, the first pass combines Greedy M0 with an incomplete λ-bounded semi-matching S; with λ=3, selected edges help form 3-augmenting paths completed by second-pass Greedy.S limits each A-vertex to degree one and each B-vertex to degree λ.Source: §6.1 · pp. 18–19
  • |A(S)| ≥ λ/(λ+1)|M*|: the bipartite algorithm’s incomplete λ-bounded semi-matching covers at least this many A-vertices.This bound holds for λ ≥ 2.Source: §6.1 · pp. 19–20

6.1 Bipartite Graphs; 6.2 Extension to General Graphs

  • 1/2+0.019 for MBM and 1/2+1/140 ≈ 1/2+0.007142 for general Maximum Matching are deterministic two-pass guarantees for any arrival order.The general-graph algorithm uses b=8.Source: §6.1 · p. 20, §6.2 · pp. 23–24

6.2 Extension to General Graphs

  • For general graphs, the first pass builds Greedy M and an incomplete b-bounded forest F, then augments M; the second pass completes length-2 paths into 3-augmenting paths.Unused forest edges are retained in MR for the second-pass construction.Source: §6.2 · pp. 20–21
  • In the general-graph analysis, each maximum-matching vertex outside F has a partner already at degree b in F, supporting a lower bound on F’s size.The constructed F is a forest with maximum degree b.Source: §6.2 · p. 22
Loading 1112.0184v3…