Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs

Olivier Fischer; Yonggang Jiang; Sagnik Mukhopadhyay; Sorrachai Yingchareonthawornchai

doi:10.1137/1.9781611978964.33

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs

Olivier Fischer^*
, Yonggang Jiang
, Sagnik Mukhopadhyay
, Sorrachai Yingchareonthawornchai

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Vertex connectivity and its variants are among the most fundamental problems in graph theory, with decades of extensive study and numerous algorithmic advances. The directed variants of vertex connectivity are usually solved by manually extending fast algorithms for undirected graphs, which has required considerable effort. In this paper, we present an extremely simple reduction from directed to undirected vertex connectivity for dense graphs. As immediate corollaries, we vastly simplify the proof for directed vertex connectivity in n^2+o(1) time [25], and obtain a parallel vertex connectivity algorithm for directed graphs with n^ω+o(1) work and n^o(1) depth, via the undirected vertex connectivity algorithm of [4].

Our reduction further extends to the weighted, all-pairs and Steiner versions of the problem. By combining our reduction with the recent subcubic-time algorithm for undirected weighted vertex cuts [10], we obtain a subcubic-time algorithm for weighted directed vertex connectivity, improving upon a three-decade-old bound [19] for dense graphs. For the all-pairs version, by combining the conditional lower bounds on the all-pairs vertex connectivity problem for directed graphs [1], we obtain an alternate proof of the conditional lower bound for the all-pairs vertex connectivity problem on undirected graphs, vastly simplifying the proof by [20].

Original language	English
Title of host publication	2026 SIAM Symposium on Simplicity in Algorithms (SOSA)
Editors	Sepehr Assadi, Eva Rotenberg
Publisher	Society for Industrial and Applied Mathematics Publications
Pages	413-420
Number of pages	8
ISBN (Electronic)	9781611978964
DOIs	https://doi.org/10.1137/1.9781611978964.33
Publication status	Published - 6 Jan 2026
Event	9th SIAM Symposium on Simplicity in Algorithms - Hyatt Regency Vancouver, Vancouver, Canada Duration: 12 Jan 2026 → 14 Jan 2026 Conference number: 9 https://www.siam.org/conferences-events/past-event-archive/sosa26/

Publication series

Name	Proceedings of the SIAM Symposium on Simplicity in Algorithms
Publisher	Society for Industrial and Applied Mathematics
ISSN (Electronic)	2688-1837

Conference

Conference	9th SIAM Symposium on Simplicity in Algorithms
Abbreviated title	SOSA 2026
Country/Territory	Canada
City	Vancouver
Period	12/01/26 → 14/01/26
Internet address	https://www.siam.org/conferences-events/past-event-archive/sosa26/

Bibliographical note

Publisher Copyright:
Copyright © 2026 by SIAM.

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1137/1.9781611978964.33Licence: None: All rights reserved

1 Preprint

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
Jiang, Y., Mukhopadhyay, S. & Yingchareonthawornchai, S., 27 Aug 2025, arXiv, 10 p.
Research output: Working paper/Preprint › Preprint

File
8 Downloads (Pure)

Cite this

Fischer, O., Jiang, Y., Mukhopadhyay, S., & Yingchareonthawornchai, S. (2026). Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs. In S. Assadi, & E. Rotenberg (Eds.), 2026 SIAM Symposium on Simplicity in Algorithms (SOSA) (pp. 413-420). (Proceedings of the SIAM Symposium on Simplicity in Algorithms). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611978964.33

Fischer, Olivier ; Jiang, Yonggang ; Mukhopadhyay, Sagnik et al. / Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs. 2026 SIAM Symposium on Simplicity in Algorithms (SOSA). editor / Sepehr Assadi ; Eva Rotenberg. Society for Industrial and Applied Mathematics Publications, 2026. pp. 413-420 (Proceedings of the SIAM Symposium on Simplicity in Algorithms).

@inproceedings{397b023630634bf6a88422cad74f8901,

title = "Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs",

abstract = "Vertex connectivity and its variants are among the most fundamental problems in graph theory, with decades of extensive study and numerous algorithmic advances. The directed variants of vertex connectivity are usually solved by manually extending fast algorithms for undirected graphs, which has required considerable effort. In this paper, we present an extremely simple reduction from directed to undirected vertex connectivity for dense graphs. As immediate corollaries, we vastly simplify the proof for directed vertex connectivity in n2+o(1) time [25], and obtain a parallel vertex connectivity algorithm for directed graphs with nω+o(1) work and no(1) depth, via the undirected vertex connectivity algorithm of [4]. Our reduction further extends to the weighted, all-pairs and Steiner versions of the problem. By combining our reduction with the recent subcubic-time algorithm for undirected weighted vertex cuts [10], we obtain a subcubic-time algorithm for weighted directed vertex connectivity, improving upon a three-decade-old bound [19] for dense graphs. For the all-pairs version, by combining the conditional lower bounds on the all-pairs vertex connectivity problem for directed graphs [1], we obtain an alternate proof of the conditional lower bound for the all-pairs vertex connectivity problem on undirected graphs, vastly simplifying the proof by [20].",

author = "Olivier Fischer and Yonggang Jiang and Sagnik Mukhopadhyay and Sorrachai Yingchareonthawornchai",

note = "Publisher Copyright: Copyright {\textcopyright} 2026 by SIAM.; 9th SIAM Symposium on Simplicity in Algorithms, SOSA 2026 ; Conference date: 12-01-2026 Through 14-01-2026",

year = "2026",

month = jan,

day = "6",

doi = "10.1137/1.9781611978964.33",

language = "English",

series = "Proceedings of the SIAM Symposium on Simplicity in Algorithms",

publisher = "Society for Industrial and Applied Mathematics Publications",

pages = "413--420",

editor = "Sepehr Assadi and Eva Rotenberg",

booktitle = "2026 SIAM Symposium on Simplicity in Algorithms (SOSA)",

address = "United States",

url = "https://www.siam.org/conferences-events/past-event-archive/sosa26/",

}

Fischer, O, Jiang, Y, Mukhopadhyay, S & Yingchareonthawornchai, S 2026, Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs. in S Assadi & E Rotenberg (eds), 2026 SIAM Symposium on Simplicity in Algorithms (SOSA). Proceedings of the SIAM Symposium on Simplicity in Algorithms, Society for Industrial and Applied Mathematics Publications, pp. 413-420, 9th SIAM Symposium on Simplicity in Algorithms, Vancouver, Canada, 12/01/26. https://doi.org/10.1137/1.9781611978964.33

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs. / Fischer, Olivier; Jiang, Yonggang; Mukhopadhyay, Sagnik et al.
2026 SIAM Symposium on Simplicity in Algorithms (SOSA). ed. / Sepehr Assadi; Eva Rotenberg. Society for Industrial and Applied Mathematics Publications, 2026. p. 413-420 (Proceedings of the SIAM Symposium on Simplicity in Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs

AU - Fischer, Olivier

AU - Jiang, Yonggang

AU - Mukhopadhyay, Sagnik

AU - Yingchareonthawornchai, Sorrachai

N1 - Conference code: 9

PY - 2026/1/6

Y1 - 2026/1/6

N2 - Vertex connectivity and its variants are among the most fundamental problems in graph theory, with decades of extensive study and numerous algorithmic advances. The directed variants of vertex connectivity are usually solved by manually extending fast algorithms for undirected graphs, which has required considerable effort. In this paper, we present an extremely simple reduction from directed to undirected vertex connectivity for dense graphs. As immediate corollaries, we vastly simplify the proof for directed vertex connectivity in n2+o(1) time [25], and obtain a parallel vertex connectivity algorithm for directed graphs with nω+o(1) work and no(1) depth, via the undirected vertex connectivity algorithm of [4]. Our reduction further extends to the weighted, all-pairs and Steiner versions of the problem. By combining our reduction with the recent subcubic-time algorithm for undirected weighted vertex cuts [10], we obtain a subcubic-time algorithm for weighted directed vertex connectivity, improving upon a three-decade-old bound [19] for dense graphs. For the all-pairs version, by combining the conditional lower bounds on the all-pairs vertex connectivity problem for directed graphs [1], we obtain an alternate proof of the conditional lower bound for the all-pairs vertex connectivity problem on undirected graphs, vastly simplifying the proof by [20].

AB - Vertex connectivity and its variants are among the most fundamental problems in graph theory, with decades of extensive study and numerous algorithmic advances. The directed variants of vertex connectivity are usually solved by manually extending fast algorithms for undirected graphs, which has required considerable effort. In this paper, we present an extremely simple reduction from directed to undirected vertex connectivity for dense graphs. As immediate corollaries, we vastly simplify the proof for directed vertex connectivity in n2+o(1) time [25], and obtain a parallel vertex connectivity algorithm for directed graphs with nω+o(1) work and no(1) depth, via the undirected vertex connectivity algorithm of [4]. Our reduction further extends to the weighted, all-pairs and Steiner versions of the problem. By combining our reduction with the recent subcubic-time algorithm for undirected weighted vertex cuts [10], we obtain a subcubic-time algorithm for weighted directed vertex connectivity, improving upon a three-decade-old bound [19] for dense graphs. For the all-pairs version, by combining the conditional lower bounds on the all-pairs vertex connectivity problem for directed graphs [1], we obtain an alternate proof of the conditional lower bound for the all-pairs vertex connectivity problem on undirected graphs, vastly simplifying the proof by [20].

UR - https://www.scopus.com/pages/publications/105033349269

U2 - 10.1137/1.9781611978964.33

DO - 10.1137/1.9781611978964.33

M3 - Conference contribution

AN - SCOPUS:105033349269

T3 - Proceedings of the SIAM Symposium on Simplicity in Algorithms

SP - 413

EP - 420

BT - 2026 SIAM Symposium on Simplicity in Algorithms (SOSA)

A2 - Assadi, Sepehr

A2 - Rotenberg, Eva

PB - Society for Industrial and Applied Mathematics Publications

T2 - 9th SIAM Symposium on Simplicity in Algorithms

Y2 - 12 January 2026 through 14 January 2026

ER -

Fischer O, Jiang Y, Mukhopadhyay S, Yingchareonthawornchai S. Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs. In Assadi S, Rotenberg E, editors, 2026 SIAM Symposium on Simplicity in Algorithms (SOSA). Society for Industrial and Applied Mathematics Publications. 2026. p. 413-420. (Proceedings of the SIAM Symposium on Simplicity in Algorithms). doi: 10.1137/1.9781611978964.33

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Research output

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs

Cite this