Average Sensitivity of Graph Algorithms

DOI10.1137/21M1399592zbMATH Open1520.68219arXiv1904.03248MaRDI QIDQ6046751FDOQ6046751

Authors: Nithin M. Varma, Yuichi Yoshida 

Publication date: 6 September 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: In modern applications of graphs algorithms, where the graphs of interest are large and dynamic, it is unrealistic to assume that an input representation contains the full information of a graph being studied. Hence, it is desirable to use algorithms that, even when only a (large) subgraph is available, output solutions that are close to the solutions output when the whole graph is available. We formalize this idea by introducing the notion of average sensitivity of graph algorithms, which is the average earth mover's distance between the output distributions of an algorithm on a graph and its subgraph obtained by removing an edge, where the average is over the edges removed and the distance between two outputs is the Hamming distance. In this work, we initiate a systematic study of average sensitivity. After deriving basic properties of average sensitivity such as composition, we provide efficient approximation algorithms with low average sensitivities for concrete graph problems, including the minimum spanning forest problem, the global minimum cut problem, the minimum $s$-$t$ cut problem, and the maximum matching problem. In addition, we prove that the average sensitivity of our global minimum cut algorithm is almost optimal, by showing a nearly matching lower bound. We also show that every algorithm for the 2-coloring problem has average sensitivity linear in the number of vertices. One of the main ideas involved in designing our algorithms with low average sensitivity is the following fact; if the presence of a vertex or an edge in the solution output by an algorithm can be decided locally, then the algorithm has a low average sensitivity, allowing us to reuse the analyses of known sublinear-time algorithms and local computation algorithms (LCAs). Using this connection, we show that every LCA for 2-coloring has linear query complexity, thereby answering an open question.

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

Recommendations

• Publication:4886061
• Average-case analysis of dynamic graph algorithms
• Dynamic graph stream algorithms in \(o(n)\) space
• Dynamic graph stream algorithms in \(o(n)\) space
• scientific article; zbMATH DE number 1263228

zbMATH Keywords

approximation algorithmsgraph algorithmssublinear algorithmsaverage sensitivity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• 10.1162/153244302760200704
• Understanding machine learning. From theory to algorithms
• Title not available (Why is that?)
• Paths, Trees, and Flowers
• Differentially private combinatorial optimization
• Theory of Cryptography
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The centrality index of a graph
• Harmony in the small-world
• Title not available (Why is that?)
• New techniques and tighter bounds for local computation algorithms
• Converting online algorithms to local computation algorithms
• A Local Computation Approximation Scheme to Maximum Matching
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Local computation algorithms for graphs of non-constant degrees
• Space-efficient local computation algorithms
• Constant-time local computation algorithms
• Local computation algorithms for spanners
• A framework for algorithm stability and its application to kinetic Euclidean MSTs
• Best of two local models: centralized local and distributed local algorithms
• Analyzing graphs with node differential privacy
• Sublinear graph augmentation for fast query implementation
• Title not available (Why is that?)
• Optimal dynamic distributed MIS
• Private analysis of graph structure
• Local algorithms for sparse spanning graphs
• Title not available (Why is that?)

This page was built for publication: Average Sensitivity of Graph Algorithms

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