Projects per year
Abstract
Graph compression or sparsification is a basic informationtheoretic and computational question. A major open problem in this research area is whether (1 + ε)approximate cutpreserving 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 connectivityc mimicking network, which preserves connectivity among k terminals exactly up to the value of c. We show that connectivityc mimicking networks with O(kc^{4}) 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 mc^{O}(c) log^{O}^{(1)} n. These results lead to the first data structures for answering fully dynamic offline cedgeconnectivity queries for c ≥ 4 in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.
Original language  English 

Title of host publication  ACMSIAM Symposium on Discrete Algorithms, SODA 2021 
Editors  Daniel Marx 
Publisher  ACM 
Pages  12061225 
Number of pages  20 
ISBN (Electronic)  9781611976465 
DOIs  
Publication status  Published  2021 
MoE publication type  A4 Article in a conference publication 
Event  ACMSIAM Symposium on Discrete Algorithms  Virtual, Online, Alexandria, United States Duration: 10 Jan 2021 → 13 Jan 2021 Conference number: 32 https://www.siam.org/conferences/cm/conference/soda21 
Publication series
Name  Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms 

Conference
Conference  ACMSIAM Symposium on Discrete Algorithms 

Abbreviated title  SODA 
Country  United States 
City  Alexandria 
Period  10/01/2021 → 13/01/2021 
Internet address 
Fingerprint
Dive into the research topics of 'Vertex sparsification for edge connectivity'. Together they form a unique fingerprint.Projects
 2 Active

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Spoerhase, J., Orgo, L. & Yingchareonthawornchai, S.
01/02/2018 → 31/01/2024
Project: EU: ERC grants

Combinatorics of Graph Packing and Online Binary Search Trees
Chalermsook, P., Uniyal, S., Obscura Acosta, N. & Jiamjitrak, W.
01/09/2017 → 31/08/2022
Project: Academy of Finland: Other research funding