Distributed Vertex Cover Reconfiguration
summary
Defines batched reconfiguration where each batch must be safe under any adversarial ordering (equivalently batch vertices form an independent set), and proves a compression: any monotone sequential schedule becomes a batched schedule with O(1/ε) batches and 1+ε approximation to the max intermediate cover. Builds distributed algorithms in the LOCAL model using a small separator decomposition (clusters diameter O(1/ε), separator size ≈ε|α Δ β|) to compute schedules in O(log* n / ε) rounds; applies to cactus, planar and bounded‑diversity cases.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:31Motivation
- 1:36Sequential Vertex Cover Reconfiguration
- 4:41Batch Vertex Cover Reconfiguration Goal: Reconfigure faster Batched reconfiguration schedule (incomplete)
- 9:38Our Results & Summary Centralized
- 14:13Sequential to Batch Compression - Proof
- 18:57Implications
- 20:44LOCAL Model [Linial; FOCS '87]
- 21:51A computer in a big big world
- 22:59Reconfiguration in the LOCAL model
- 24:32(d,x)-Separator Decomposition
- 26:11Using the Decomposition
- 30:09Approximation analysis Schedule bounds
- 31:22Computing the Decomposition
related talks
39mSketching and Randomization for Distributed Submodular and Coverage Optimization
46mDistributed Graph Techniques in the MPC Model
30mParallelization by Approximation
23mTowards General and Tight Hardness Results for Graph Problems
19mLook Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
19mDistributed load balancing: a new framework and improved guarantees
27mDetect, Decide, Fence: Resolving Netsplits in 3-AZ Stretch Cluster