2019/10/23 by Yang P. Liu, Richard Peng, Liu, Yang P. +3 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · Materials Science · #Complexity and Algorithms in Graphs #Advanced biosensing and bioanalysis techniques #Graphene research and applications
paper · pdf · doi:10.48550/arxiv.1910.10359
We show the existence of O(f(c)k) sized vertex sparsifiers that preserve all edge-connectivity values up to c between a set of k terminal vertices, where f(c) is a function that only depends on c, the edge-connectivity value. This construction is algorithmic: we also provide an algorithm whose running time depends linearly on k, but exponentially in c. It implies that for constant values of c, an offline sequence of edge insertions/deletions and c-edge-connectivity queries can be answered in polylog time per operation. These results are obtained by combining structural results about minimum terminal separating cuts in undirected graphs with recent developments in expander decomposition based methods for finding small vertex/edge cuts in graphs.