惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

IT之家
IT之家
博客园_首页
S
SegmentFault 最新的问题
罗磊的独立博客
博客园 - 【当耐特】
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
阮一峰的网络日志
阮一峰的网络日志
D
Docker
雷峰网
雷峰网
Google DeepMind News
Google DeepMind News
博客园 - 司徒正美
V
V2EX
大猫的无限游戏
大猫的无限游戏
V
Visual Studio Blog
腾讯CDC
宝玉的分享
宝玉的分享
酷 壳 – CoolShell
酷 壳 – CoolShell
人人都是产品经理
人人都是产品经理
T
Tailwind CSS Blog
Vercel News
Vercel News
H
Help Net Security
博客园 - Franky
D
DataBreaches.Net
aimingoo的专栏
aimingoo的专栏

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
Vital Edges for (s,t)-mincut: Efficient Algorithms, Compa...
Surender Baswana, Koustav Bhanja · 2023-10-19 · via cs.DS updates on arXiv.org

Let G be a directed weighted graph (DiGraph) on n vertices and m edges with source s and sink t. An edge in G is vital if its removal reduces the capacity of (s,t)-mincut. Since the seminal work of Ford and Fulkerson, a long line of work has been done on computing the most vital edge and all vital edges of G. Unfortunately, after 60 years, the existing results are for undirected or unweighted graphs. We present the following result for DiGraph, which solves an open problem stated by Ausiello et al. 1. There is an algorithm that computes all vital edges as well as the most vital edge of G using O(n) maxflow computations. Vital edges play a crucial role in the design of Sensitivity Oracle (SO) for (s,t)-mincut. For directed graphs, the only existing SO is for unweighted graphs by Picard and Queyranne. We present the first and optimal SO for DiGraph. 2. (a) There is an O(n) space SO that can report in O(1) time the capacity of (s,t)-mincut and (b) an O($n^2$) space SO that can report an (s,t)-mincut in O(n) time after failure/insertion of an edge. For unweighted graphs, Picard and Queyranne designed an O(m) space DAG that stores and characterizes all mincuts for all vital edges. Conversely, there is a set containing at most n-1 (s,t)-cuts such that at least one mincut for every vital edge belongs to the set. We generalize these results for DiGraph. 3. (a) There is a set containing at most n-1 (s,t)-cuts such that at least one mincut for every vital edge is present in the set. (b) We design two compact structures for storing and characterizing all mincuts for all vital edges, (i) O(m) space DAG for partial characterization and (ii) O(mn) space structure for complete characterization. To arrive at our results, we develop new techniques, especially a generalization of maxflow-mincut theorem by Ford and Fulkerson, which might be of independent interest.