Average Sensitivity of Graph Algorithms

DOI10.1137/21M1399592zbMATH Open1520.68219MaRDI QIDQ6046751FDOQ6046751

Authors Nithin M. Varma, Yuichi Yoshida 

Publication date 6 September 2023

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

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

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)

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.

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

Cites Work

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

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)