Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches

DOI10.4230/LIPICS.FSTTCS.2015.52MaRDI QIDQ5278310zbMATH OpenOpenAlexFDO

Authors Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen

Publication date 13 July 2017

Full work available at URL https://arxiv.org/abs/1510.03252

zbMATH Keywords

maximum matchingssmall-space algorithmsvertex sparsifiers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) General topics in the theory of algorithms (68W01) Programming involving graphs or networks (90C35)

Abstract: In this paper, we introduce a new model for sublinear algorithms called emph{dynamic sketching}. In this model, the underlying data is partitioned into a large emph{static} part and a small emph{dynamic} part and the goal is to compute a summary of the static part (i.e, a emph{sketch}) such that given any emph{update} for the dynamic part, one can combine it with the sketch to compute a given function. We say that a sketch is emph{compact} if its size is bounded by a polynomial function of the length of the dynamic data, (essentially) independent of the size of the static part. A graph optimization problem $P$ in this model is defined as follows. The input is a graph $G(V,E)$ and a set $TsubseteqV$ of $k$ terminals; the edges between the terminals are the dynamic part and the other edges in $G$ are the static part. The goal is to summarize the graph $G$ into a compact sketch (of size poly$(k)$) such that given any set $Q$ of edges between the terminals, one can answer the problem $P$ for the graph obtained by inserting all edges in $Q$ to $G$, using only the sketch. We study the fundamental problem of computing a maximum matching and prove tight bounds on the sketch size. In particular, we show that there exists a (compact) dynamic sketch of size $O(k^2)$ for the matching problem and any such sketch has to be of size $Omega(k^2)$. Our sketch for matchings can be further used to derive compact dynamic sketches for other fundamental graph problems involving cuts and connectivities. Interestingly, our sketch for matchings can also be used to give an elementary construction of a emph{cut-preserving vertex sparsifier} with space $O(k{C}^2)$ for $k$-terminal graphs; here $C$ is the total capacity of the edges incident on the terminals. Additionally, we give an improved lower bound (in terms of $C$) of $Omega(C/logC)$ on size of cut-preserving vertex sparsifiers.

Recommendations

• Optimal lower bounds for sketching graph cuts
• Sketching cuts in graphs and hypergraphs
• Fast dynamic graph algorithms for parameterized problems
• Randomized sketching algorithms for low-memory dynamic optimization
• The State of the Art in Dynamic Graph Algorithms
• scientific article; zbMATH DE number 1617242
• Dynamic Parallel and Distributed Graph Cuts
• Approximating graph-constrained max-cut
• Dynamic Graph Cuts in Parallel

Cited in

(5)

• On sketching quadratic forms
• Sketching cuts in graphs and hypergraphs
• Sketches and computation – II: dynamic evaluation and applications
• Optimal lower bounds for sketching graph cuts
• Boundaried kernelization

This page was built for publication: Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5278310)