PaperlayerView exact revision on arXiv

Source-linked AI summary

Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching

Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano

arXiv:1412.1318v1cs.DS

TL;DR

Fast deterministic maintenance of approximate vertex cover and matching remains an open challenge against faster randomized update bounds. The paper uses fractional matching and graph kernels to maintain these solutions dynamically. It gives improved approximation and update guarantees, including near-optimal vertex-cover maintenance under the unique games conjecture.

  • Problem

    Deterministic dynamic vertex-cover and matching structures had slower update bounds than randomized ones, and the paper asks whether constant-factor approximations can be maintained with polylogarithmic updates.

    Source: §1 · p. 3, §1.2 · p. 4

  • Method

    The paper adapts a hierarchical vertex-cover framework by using a fractional matching as its dual certificate and introduces dynamically maintainable kernels for integral matching.

    Source: §1.3 · p. 5

  • Results

    A deterministic (2+ε)-approximate vertex cover takes O(log n/ε^2) amortized update time; maximum matching takes O(min(√n/ε,m^1/3/ε^2)) amortized time for (3+ε) approximation or O(m^1/3/ε^2) worst-case time for (4+ε).

    Source: §1.2 · p. 4

  • Takeaways & Limitations

    The vertex-cover structure is near-optimal under the unique games conjecture, and the matching structures are the first deterministic ones with update time sublinear in the number of nodes.

    Source: §1.2 · p. 4

    The amortized update-time overview assumes sufficiently large constant values of α and β.

    Source: §2.4 · p. 10

Abstract

from arXiv · show

We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph $G = (V,E)$, with $|V| = n$ and $|E| =m$, in $o(\sqrt{m}\,)$ time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a $(2+\eps)$ approximation in $O(\log n/\eps^2)$ amortized time per update. For maximum matching, we show how to maintain a $(3+\eps)$ approximation in $O(\min(\sqrt{n}/\epsilon, m^{1/3}/\eps^2))$ {\em amortized} time per update, and a $(4+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em worst-case} time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld from STOC' 2010.

1 Introduction

The introduction frames fast deterministic maintenance of approximate vertex cover and matching as an open challenge, then presents improved guarantees and two complementary techniques. The approach combines fractional matching with a bounded-degree kernel that approximately preserves maximum matching size.

1 Introduction

  • A greedy maximal matching gives a 2-approximation to both maximum matching and minimum vertex cover, while under the unique games conjecture minimum vertex cover cannot be efficiently approximated within a factor better than 2.The static Micali–Vazirani maximum-matching algorithm runs in O(m√n) time.Source: §1 · p. 3

1.1 Previous work.

  • Prior dynamic approaches included randomized O(log n) amortized updates for 2-approximations and deterministic O(√m) worst-case updates for stronger matching approximations.Baswana, Gupta, and Sen [2] give the randomized maximal-matching approach; Neiman and Solomon [12] and Gupta and Peng give deterministic matching structures.Source: §1.1 · p. 3

1.2 Our results.

  • The paper targets the gap between deterministic O(√m) and randomized O(log n) update bounds, addressing the question of deterministic constant-factor approximation with polylogarithmic updates.The question is attributed to Onak and Rubinfeld.Source: §1 · p. 3, §1.2 · p. 4
  • Minimum vertex cover admits a deterministic (2+ε)-approximation in O(log n/ε^2) amortized time; maximum matching admits (3+ε) in O(min(√n/ε,m^1/3/ε^2)) amortized and (4+ε) in O(m^1/3/ε^2) worst-case time per update.The vertex-cover guarantee is near-optimal under the unique games conjecture.Source: §1.2 · p. 4

1.3 Our techniques.

  • Replacing the matching dual certificate in Onak and Rubinfeld’s hierarchical vertex-cover framework with a fractional matching yields deterministic maintenance and improves its approximation and update bounds.A deterministic fractional matching spreads an edge’s contribution across incident edges, allowing deletions to reduce a node’s contribution by at most a factor of two over the stated interval.Source: §1.3 · pp. 4–5
  • A kernel is a dynamically maintainable subgraph with bounded degree at each node that approximately preserves the original graph’s maximum matching size.The paper presents kernels as the basis for its improved deterministic update times for approximate integral matching.Source: §1.3 · p. 5

2 Deterministic Fully Dynamic Vertex Cover

This section presents a deterministic fully dynamic vertex-cover structure based on a weighted hierarchical partition and recovery routines. It analyzes the routines’ amortized update costs using potential accounting, including how potential decreases pay for FIX calls and support progress in Case 2 of Theorem 2.14.

2 Deterministic Fully Dynamic Vertex Cover

  • For every ϵ ∈ (0, 1], the deterministic structure maintains a (2 + ϵ)-approximate vertex cover in O(log n/ϵ^2) amortized update time.Source: §2 · p. 6

2.1 The (α, β)-partition and its properties.

  • An (α, β)-partition satisfying Invariant 2.4 yields a feasible vertex cover of size at most 2αβ times the minimum; the cover consists of nodes with weight at least one.Source: §2.1 · p. 7

2.2 Handling the insertion/deletion of an edge.

  • When an edge update makes endpoints dirty, RECOVER adjusts node levels until all nodes are clean and Invariant 2.4 holds; scaled edge weights implicitly form a fractional matching dual certificate.This implicit certificate avoids maintaining a matching data structure, which the passage says prior work needed to randomize.Source: §2.2 · pp. 8–9

2.3 Data structures.

  • The implementation tracks node levels and weights, neighborhood lists, dirty-node status, and bidirectional pointers linking each edge to its endpoints’ neighborhood lists.Source: §2.3 · p. 9

2.4 Bounding the amortized update time: An overview

  • With α = 1 + 3ϵ and β = 1 + ϵ, t edge updates take O(t log n/ϵ^2) time, yielding a (2 + 14ϵ)-approximation through potential-based analysis of level adjustments.The overview bounds the number of affected existing edges per level change and uses node and edge tokens as potential.Source: §2.4 · pp. 9–11

2.5 Implementation details

  • Edge insertions and deletions each take Θ(1) time apart from calls to FIX, which are separately charged and analyzed.Source: §2.5 · p. 12
  • MOVE-UP and MOVE-DOWN each take Θ(1 + Dv(0, k)) time, where k is the node’s level before the move.The two routines increment and decrement the node’s level, respectively.Source: §2.5 · pp. 12–14
  • The algorithm can answer whether a node is in the cover and report the cover size in Θ(1) time, or enumerate the cover in O(|V*|) time.Membership is determined by whether WEIGHT[v] ≥ 1; the size and enumeration queries use maintained counters and a linked list.Source: §2.5 · pp. 14, 16

2.6 Bounding the amortized update time: Detailed analysis

  • The potential-accounting analysis bounds handling t edge updates by O(tL/ϵ), with a deposit of at most 20L/ϵ per update.The analysis separately bounds potential increases by 18L/ϵ for an insertion and 4L/ϵ for a deletion.Source: §2.6 · pp. 16–17

2.6.1 Analysis of the FIX(v) subroutine

  • Each FIX(v) call decreases the potential by more than zero and by at least its runtime.FIX moves a dirty node up when its weight exceeds αβ and down when its weight is below 1.Source: §2.5 · p. 12, §2.6.1 · p. 17
  • Lemma 2.20 bounds T by βk; FIX(v) does so through MOVE-DOWN(v), whose runtime is Θ(1 + Dv(0, k)).The analysis also states Dv(0, k) ≤ βk.Source: §2.6.1 · p. 19
  • For every u ∈ Nv, δΨ(u) ≥ 0; δΦ(u, v) is 0 for u ∈ Nv(k, L) and −(1 + ϵ) for u ∈ Nv(0, k − 1).Source: §2.6.1 · p. 20
  • In Case 2, both scenarios split by α − βx − y yield δB ≥ βk, completing Theorem 2.14 using Lemma 2.20.The proof considers α − βx − y < 0 and α − βx − y ≥ 0.Source: §2.6.1 · p. 21

3 Dynamic Matching: Preliminaries

The paper maintains approximate maximum matchings in dynamic graphs using two ideas: matching is easier in bounded-degree graphs, and kernels approximately preserve maximum matching size while having bounded degree.

3 Dynamic Matching: Preliminaries

  • The three dynamic matching algorithms build on maintaining good approximate matchings in bounded-degree graphs.The paper presents this as the first of two key ideas used by all three algorithms.Source: §3 · p. 21
  • A kernel is a bounded-degree subgraph that approximately preserves the size of the graph’s maximum matching.The paper describes a static kernel-building algorithm and data structures for maintaining a kernel dynamically.Source: §3 · p. 21
  • The data structures explicitly maintain matched edges and support constant-time matching-size, edge-membership, and node-mate queries.They can also report all matched edges in O(1) time per edge.Source: §3 · p. 22

3.1 Maintaining an approximate matching in a bounded degree graph.

In bounded-degree dynamic graphs, the section gives update bounds for maintaining maximal and approximate matchings. Its main construction maintains a matching with no augmenting path shorter than five, using O(∆) worst-case time per update.

3.1 Maintaining an approximate matching in a bounded degree graph.

  • For a dynamic graph whose maximum degree is bounded by ∆, the algorithm maintains a maximal matching with O(1) edge-insertion time and O(∆) edge-deletion time.When a matched edge is deleted, it scans the endpoints’ neighbors for unmatched nodes and adds replacement edges when available.Source: §3.1 · p. 22
  • O(∆) worst-case time per update maintains a matching with no augmenting path shorter than five, yielding a 3/2-approximation in a graph of maximum degree ∆.The theorem states the bound for both insertions and deletions.Source: §3.1 · pp. 22–23

3.1.1 Proof of Theorem 3.4

  • The algorithm’s lists and pointer matrices support constant-time updates to neighbor and free-neighbor lists.It stores each node’s neighbors and unmatched neighbors in doubly linked lists, with matrices pointing to list positions.Source: §3.1.1 · p. 23
  • After an edge insertion, the algorithm resolves any newly created augmenting path of length one or three; only the case with one matched and one unmatched endpoint needs O(∆) time.If both endpoints are unmatched it matches them; if both are matched it makes no change.Source: §3.1.1 · p. 23
  • After a matched-edge deletion, FIND-MATE and RESOLVE restore the guarantee that every augmenting path has length at least five, in O(∆) time.FIND-MATE handles free neighbors; RESOLVE addresses any remaining length-three augmenting path.Source: §3.1.1 · pp. 24–25, Figure 13 · p. 24

3.2 The kernel and its properties.

The kernel is a bounded-degree subgraph that preserves enough structure to approximate maximum matching. The section proves approximation guarantees for matchings in the kernel and gives a construction showing that one bound is tight.

3.2 The kernel and its properties.

  • A (ϵ, c)-kernel has at most (1 + ϵ)c friends per node, at least (1 − ϵ)c friends per tight node, and includes every edge between slack nodes.These invariants make the kernel a bounded-degree subgraph that approximately preserves maximum-matching size.Source: §3.2 · p. 25

3.2.1 Proof of Theorem 3.9.

  • A maximal matching in an (ϵ, c)-kernel is a (4 + 6ϵ)-approximation to maximum matching in the original graph.The proof bounds free tight nodes by charging them to matched vertices, then uses the kernel’s slack-node invariant to bound omitted matching edges.Source: §3.2 · p. 25, §3.2.1 · pp. 25–26

3.2.2 Proof of Theorem 3.10.

  • A matching with no augmenting path shorter than five in an (ϵ, c)-kernel is a (3 + 3ϵ)-approximation to maximum matching in the original graph.The proof uses the absence of length-three augmenting paths to bound free tight nodes charged to each matched edge.Source: §3.2 · p. 25, §3.2.2 · p. 26

3.2.3 Proof of Theorem 3.11.

  • For every positive even c, a (1/c, c)-kernel can have a maximal matching M while the graph’s maximum matching is at least 4 times larger.The construction has |M| = c/2 and a matching of size 2c.Source: §3.2 · p. 25, §3.2.3 · p. 27

3.3 An algorithm for building a kernel in a static graph.

The section gives a linear-time algorithm for constructing a (0, c)-kernel of a static graph, with exact friend-count properties for tight and slack nodes.

3.3 An algorithm for building a kernel in a static graph.

  • For every c ≥ 1, the algorithm computes a (0, c)-kernel in O(|E|) time, with exactly c friends at each tight node and fewer than c at each slack node.It scans edges and includes an edge when both endpoints have fewer than c friends.Source: §3.3 · p. 28

3.4 Data structures for representing a kernel in a dynamic graph.

The kernel representation stores each node’s type, friends, and friend count, with edge pointers supporting constant-time kernel-edge changes.

3.4 Data structures for representing a kernel in a dynamic graph.

  • Each node stores its tight-or-slack type, a doubly linked list of friends, and a counter for its friend count.Each kernel edge stores pointers to its two occurrences in the endpoint friend lists, enabling O(1)-time insertion or deletion.Source: §3.4 · pp. 28–29

4 (3 + ϵ)-approximate matching in O(√n/ϵ) amortized update time

The section maintains a (3 + ϵ)-approximate maximum matching by updating a bounded-degree kernel and a matching within it. Kernel refills and matching updates together give O(√n/ϵ) amortized update time.

4.2 Maintaining the kernel κ(G).

  • The kernel remains an (ϵ, √n)-kernel by refilling a tight node when its friend count falls below (1 − ϵ)√n.A refill may take O(n) time, but occurs only after the node loses at least ϵ√n friends, yielding O(√n/ϵ) amortized kernel-update time.Source: §4.1 · p. 29, §4.2 · p. 31

4 (3 + ϵ)-approximate matching in O(√n/ϵ) amortized update time

  • A deterministic data structure maintains a (3 + ϵ)-approximate matching in O(√n/ϵ) amortized update time.It preprocesses a (0, √n)-kernel and a matching with no augmenting path shorter than five, then updates both as the graph changes.Source: §4.1 · p. 29, §4 · p. 29

4.2 Maintaining the kernel κ(G).

  • Ignoring REFILL-NOW-FRIENDS calls, each edge insertion or deletion in G takes O(1) worst-case time; across updates, each node’s refill-call frequency is at most 1/(ϵ√n) per incident deletion.Source: §4.2 · pp. 30–31

4.3 Maintaining the matching M in κ(G).

  • Maintaining the kernel matching also takes O(√n/ϵ) amortized time per graph update, preserving the no-short-augmenting-path condition.The resulting kernel and matching satisfy the condition used to obtain the (3 + ϵ) approximation.Source: §4.3 · pp. 31–32

5 (3 + ϵ)-approximate matching in O(m1/3/ϵ2) amortized update time

The algorithm maintains a (3 + ϵ)-approximate matching in O(m1/3/ϵ2) amortized update time by maintaining a kernel and matching across phases. The kernel stays an (ϵ, c)-kernel throughout each phase, with c = m1/3.

5.1 Overview of our approach.

  • Each phase starts from a (0, c)-kernel and a 3/2-approximate matching, then updates both structures as the graph changes.The kernel is rebuilt at the beginning of each phase, and its preprocessing takes O(m) time.Source: §5.1 · p. 32
  • O(m1/3/ϵ2) amortized update time maintains a (3 + ϵ)-approximate matching.Here m is the edge count at the phase start.Source: §5 · p. 32, §5.1 · p. 33

5.2 Algorithms for maintaining the kernel during a phase.

  • O(c) worst-case time per graph update maintains an (ϵ, c)-kernel, with at most O(ϵ2c2) kernel updates during a phase.The kernel remains an (ϵ, c)-kernel throughout the phase.Source: §5.2 · p. 33

5.2.1 Handling an edge insertion in G during the phase.

  • An edge insertion causes at most one kernel edge insertion and one deletion, and the insertion procedure runs in O(1) worst-case time.The procedure updates endpoint neighbor lists and weights, then updates their status and kernel relationships.Source: §5.2.1 · p. 33

5.2.2 Handling an edge deletion in G during the phase.

  • An edge deletion causes at most O(ϵc) kernel edge insertions and one deletion, and the procedure runs in O(c) worst-case time.A tight node is refilled when its friend count falls below (1 − ϵ)c.Source: §5.2.2 · p. 34

5.2.3 Proof of Theorem 5.2.

  • At most ϵc calls to REFILL during a phase bound the increase in each node’s friends and keep the kernel’s friend counts within the required invariant.Each call corresponds to a tight node losing at least ϵc friends; deletions can cause at most two such losses per update.Source: §5.2.3 · pp. 34–35

6 (4 + ϵ)-approximate matching in O(m1/3/ϵ2) worst-case update time

The algorithm maintains a (4 + ϵ)-approximate matching with O(m1/3/ϵ2) worst-case update time. It uses background rebuilding of a kernel and maximal matching while maintaining approximate structures for the current phase.

6.1 Overview of our approach.

  • Background rebuilding replaces rebuilding from scratch at phase boundaries, allowing the algorithm to bound work in the worst case.The algorithm inserts O(m/(ϵ2c2)) edges into the background graph and its kernel during each update.Source: §6.1 · p. 36
  • O(m1/3/ϵ2) worst-case update time maintains a (4 + ϵ)-approximate matching.The guarantee follows from maintaining a maximal matching in a kernel during each phase.Source: §6.1 · pp. 36–37, §6 · p. 36

6.2 Algorithm for maintaining and building the kernel during each phase.

  • The epoch update algorithm handles insertions in O(1) worst-case time and deletions in O(c), while preserving a (λ + ϵ, c)-kernel.Insertions cause at most one kernel insertion; deletions cause at most O(λc) insertions and one deletion.Source: §6.2 · p. 37

6.2.1 Dealing with the current phase

  • O(c) time per update maintains the current phase’s kernel as a (2ϵ, c)-kernel and its matching as maximal, yielding a (4 + ϵ)-approximation.The maximal matching is maintained with constant-time updates per kernel edge insertion.Source: §6.1 · p. 36, §6.2.1 · p. 37

6.2.2 Preparing for the next phase.

  • O(m1/3/ϵ2) work per update builds the next phase’s kernel in the background, which becomes an (ϵ, c)-kernel when the phase ends.At phase end, G* is identical to G.Source: §6.2.2 · pp. 38–39

6.2.3 Handling an edge insertion into G during the epoch.

  • An edge insertion into G takes O(1) worst-case time and causes at most one kernel edge insertion and one deletion.The insertion procedure updates neighbor lists before processing the edge.Source: §6.2.3 · p. 39

6.2.4 Handling an edge deletion in G during the epoch.

  • An edge deletion takes O(c) worst-case time and causes at most O(λc) kernel edge insertions and one deletion.REFILL-NOW is invoked when a tight node’s friend count falls below (1 − λ − ϵ)c.Source: §6.2.4 · p. 40

6.2.5 Proof of Theorem 6.3

  • At most λc REFILL-NOW calls per epoch bound friend-count growth and help preserve the kernel’s (λ + ϵ, c) guarantee.Each call corresponds to a tight node losing at least λc friends; an epoch contains at most λ2c2/2 deletions.Source: §6.2 · p. 37, §6.2.5 · p. 41
Loading 1412.1318v1…