Vertex Sparsification for Edge Connectivity in Polynomial Time

2020/11/30 by Yang P. Liu, Liu, Yang P. · 2 citations
Computer Science · Engineering · Materials Science · #Advanced Memory and Neural Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graphene research and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2011.15101

openalex publication_date 2020/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Chalermsook et al. (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 \widetildeO(kc³) edges exist and can be constructed in polynomial time in n and c, improving over the results of Chalermsook et al. (SODA 2021) for any c ≥ log n, whose runtimes depended exponentially on c.

Citations

• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Quasipolynomial multicut-mimicking networks and kernelization of\n multiway cut problems

Cited by

• Notes on the Linear Algebraic View of Regularity Lemmas
• All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs

Related

• Vertex Sparsification for Edge Connectivity
• Vertex Sparsifiers for c-Edge Connectivity
• Vertex Sparsifiers for Hyperedge Connectivity
• Fully Dynamic s-t Edge Connectivity in Subpolynomial Time
• Refined Vertex Sparsifiers of Planar Graphs