Vertex sparsification for edge connectivity

Loading...
Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa

Date

Major/Subject

Mcode

Degree programme

Language

en

Pages

20

Series

ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pp. 1206-1225, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

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.

Description

| openaire: EC/H2020/759557/EU//ALGOCom

Keywords

Other note

Citation

Chalermsook, P, Das, S, Kook, Y, Laekhanukit, B, Liu, Y P, Peng, R, Sellke, M & Vaz, D 2021, Vertex sparsification for edge connectivity. in D Marx (ed.), ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, pp. 1206-1225, ACM-SIAM Symposium on Discrete Algorithms, Alexandria, Virginia, United States, 10/01/2021. https://doi.org/10.1137/1.9781611976465.74