Cover Image

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fischer, Olivier, Jiang, Yonggang, Mukhopadhyay, Sagnik, Yingchareonthawornchai, Sorrachai
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
by: Jiang, Yonggang, et al.
Published: (2025)

Hardness Amplification for Dynamic Binary Search Trees
by: Jiang, Shunhua, et al.
Published: (2024)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

A Little Clairvoyance Is All You Need
by: Gupta, Anupam, et al.
Published: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
by: Gupta, Anupam, et al.
Published: (2026)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
by: Jiang, Yonggang, et al.
Published: (2025)

Shortcuts and Transitive-Closure Spanners Approximation
by: Chalermsook, Parinya, et al.
Published: (2025)

The Connected k-Vertex One-Center Problem on Graphs
by: Zhang, Jingru
Published: (2024)

Sandpile Prediction on Undirected Graphs
by: Chang, Ruinian, et al.
Published: (2023)

New Oracles and Labeling Schemes for Vertex Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Network Design on Undirected Series-Parallel Graphs
by: Bansal, Ishan, et al.
Published: (2024)

Personalized PageRank Estimation in Undirected Graphs
by: Bertram, Christian, et al.
Published: (2026)

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
by: Wang, Hanzhi
Published: (2024)

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
by: Biedl, Therese, et al.
Published: (2024)

DAG Projections: Reducing Distance and Flow Problems to DAGs
by: Haeupler, Bernhard, et al.
Published: (2026)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
by: Çivril, Ali
Published: (2024)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
by: Roditty, Liam, et al.
Published: (2025)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
by: Haeupler, Bernhard, et al.
Published: (2025)

Space Complexity of Vertex Connectivity Oracles
by: Pettie, Seth, et al.
Published: (2022)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
by: Brand, Jan van den, et al.
Published: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
by: Neuwohner, Meike, et al.
Published: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
by: Bhanja, Koustav, et al.
Published: (2025)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
by: Li, Xizhe, et al.
Published: (2026)

On Computing Vertex Connectivity of 1-Plane Graphs
by: Biedl, Therese, et al.
Published: (2022)

Cluster Vertex Deletion on Chordal Graphs
by: Cao, Yixin, et al.
Published: (2026)

Undirected 3-Fault Replacement Path in Nearly Cubic Time
by: Chi, Shucheng, et al.
Published: (2024)

Undirected Replacement Paths: Dual Fault Reduces to Single Source
by: Nogler, Jakob, et al.
Published: (2026)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
by: Anand, Aditya, et al.
Published: (2025)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
by: Long, Yaowei, et al.
Published: (2024)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
by: Goldmann, Lito, et al.
Published: (2023)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
by: Fischer, Nick
Published: (2026)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
by: Çivril, Ali
Published: (2023)

A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
by: Xiong, Ziliang, et al.
Published: (2024)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
by: Yan, Shuyi
Published: (2025)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
by: Neiman, Ofer, et al.
Published: (2026)

Connectivity Oracles for Predictable Vertex Failures
by: Hu, Bingbing, et al.
Published: (2023)

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
by: Parter, Merav, et al.
Published: (2024)