Vertex sparsification for edge connectivity

Parinya Chalermsook*, Syamantak Das, Yunbum Kook, Bundit Laekhanukit, Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Abstract

Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether (1 + ε)-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter c, find a smaller graph, which we call connectivity-c mimicking network, which preserves connectivity among k terminals exactly up to the value of c. We show that connectivity-c mimicking networks with O(kc4) edges exist and can be found in time m(c log n)O(c). We also give a separate algorithm that constructs such graphs with k · O(c)2c edges in time mcO(c) logO(1) n. These results lead to the first data structures for answering fully dynamic offline c-edge-connectivity queries for c ≥ 4 in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.

Original languageEnglish
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherACM
Pages1206-1225
Number of pages20
ISBN (Electronic)9781611976465
DOIs
Publication statusPublished - 2021
MoE publication typeA4 Article in a conference publication
EventACM-SIAM Symposium on Discrete Algorithms - Virtual, Online, Alexandria, United States
Duration: 10 Jan 202113 Jan 2021
Conference number: 32
https://www.siam.org/conferences/cm/conference/soda21

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

ConferenceACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA
CountryUnited States
CityAlexandria
Period10/01/202113/01/2021
Internet address

Fingerprint

Dive into the research topics of 'Vertex sparsification for edge connectivity'. Together they form a unique fingerprint.

Cite this