Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.83
URN: urn:nbn:de:0030-drops-175863
URL: https://drops.dagstuhl.de/opus/volltexte/2023/17586/
Liu, Yang P.
Vertex Sparsification for Edge Connectivity in Polynomial Time
| pdf-format: |
|
Abstract
An important open question in the area of vertex sparsification is whether (1+ε)-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. The work [Parinya Chalermsook et al., 2021] (SODA 2021) introduced a relaxation called connectivity-c mimicking networks, which asks to construct a vertex sparsifier which preserves connectivity among k terminals exactly up to the value of c, and showed applications to dynamic connectivity data structures and survivable network design. We show that connectivity-c mimicking networks with Õ(kc³) edges exist and can be constructed in polynomial time in n and c, improving over the results of [Parinya Chalermsook et al., 2021] for any c ≥ log n, whose runtimes depended exponentially on c.
BibTeX - Entry
@InProceedings{liu:LIPIcs.ITCS.2023.83,
author = {Liu, Yang P.},
title = {{Vertex Sparsification for Edge Connectivity in Polynomial Time}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {83:1--83:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17586},
URN = {urn:nbn:de:0030-drops-175863},
doi = {10.4230/LIPIcs.ITCS.2023.83},
annote = {Keywords: Vertex-sparsification, edge-connectivity, Gammoids}
}
| Keywords: | Vertex-sparsification, edge-connectivity, Gammoids | |
| Seminar: | 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) | |
| Issue date: | 2023 | |
| Date of publication: | 01.02.2023 |
