research-article

Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams

Authors:

Naonori Kakimura,

Naoyuki Kamiyama,

Yusuke Kobayashi,

Shun-Ichi Maezawa,

Yoshio Okamoto,

Kenta OzekiAuthors Info & Claims

ACM Transactions on Algorithms, Volume 19, Issue 1

Article No.: 6, Pages 1 - 22

https://doi.org/10.1145/3561302

Published: 20 February 2023 Publication History

Abstract

We initiate the study of k-edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2k-edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge connectivity, and the final orientation is k-edge connected. This yields an “edge-flip based” new proof of Nash-Williams’ theorem: A undirected graph G has a k-edge-connected orientation if and only if G is 2k-edge connected. As another consequence of the theorem, we prove that the edge-flip graph of k-edge-connected orientations of an undirected graph G is connected if G is (2k+2)-edge connected. This has been known to be true only when k=1.

References

[1]

Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber. 2021. Flip distances between graph orientations. Algorithmica 83, 1 (2021), 116–143.

Digital Library

[2]

Alex R. Berg and Tibor Jordán. 2006. Two-connected orientations of Eulerian graphs. J. Graph Theory 52, 3 (2006), 230–242.

[3]

Attila Bernáth, Satoru Iwata, Tamás Király, Zoltán Király, and Zoltán Szigeti. 2008. Recent results on well-balanced orientations. Discr. Optim. 5, 4 (2008), 663–676.

Digital Library

[4]

Joseph Cheriyan, Olivier Durand de Gevigney, and Zoltán Szigeti. 2014. Packing of rigid spanning subgraphs and spanning trees. J. Combin. Theory Ser. B 105 (2014), 17–25.

Digital Library

[5]

Olivier Durand de Gevigney. 2020. On Frank’s conjecture on \(k\) -connected orientations. J. Combin. Theory Ser. B 141 (2020), 105–114.

Digital Library

[6]

András Frank. 1982. An algorithm for submodular functions on graphs. In Bonn Workshop on Combinatorial Optimization, Achim Bachem, Martin Grötschel, and Bemhard Korte (Eds.). North-Holland Mathematics Studies, Vol. 66. North-Holland, 97–120.

[7]

András Frank. 1982. A note on \(k\) -strongly connected orientations of an undirected graph. Discr. Math. 39, 1 (1982), 103–104.

Digital Library

[8]

András Frank. 1993. Applications of submodular functions. In Surveys in Combinatorics, 1993, Keith Walker (Ed.). Cambridge University Press, 85–136.

[9]

András Frank. 1996. Connectivity and network flows. In Handbook of Combinatorics. Vol. 1. MIT Press, 111–177.

[10]

András Frank. 2011. Connections in Combinatorial Optimization. Oxford University Press.

[11]

András Frank, Tamás Király, and Zoltán Király. 2003. On the orientation of graphs and hypergraphs. Discr. Appl. Math. 131, 2 (2003), 385–400.

Digital Library

[12]

Komei Fukuda, Alain Prodon, and Tadashi Sakuma. 2001. Notes on acyclic orientations and the shelling lemma. Theor. Comput. Sci. 263, 1–2 (2001), 9–16.

Digital Library

[13]

Takuro Fukunaga. 2012. Graph orientations with set connectivity requirements. Discr. Math. 312, 15 (2012), 2349–2355.

[14]

Harold N. Gabow. 1994. Efficient splitting off algorithms for graphs. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, Frank Thomson Leighton and Michael T. Goodrich (Eds.). ACM, 696–705.

Digital Library

[15]

Curtis Greene and Thomas Zaslavsky. 1983. On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans. Am. Math. Soc. 280 (1983), 97–126.

[16]

S. L. Hakimi. 1965. On the degrees of the vertices of a directed graph. J. Frankl. Inst. 279, 4 (1965), 290–308.

[17]

Matthew J. Hausknecht, Tsz-Chiu Au, Peter Stone, David Fajardo, and S. Travis Waller. 2011. Dynamic lane reversal in traffic management. In Proceedings of the 14th International IEEE Conference on Intelligent Transportation Systems (ITSC’11). IEEE, 1929–1934.

[18]

John E. Hopcroft and Robert Endre Tarjan. 1973. Efficient algorithms for graph manipulation (algorithm 447). Commun. ACM 16, 6 (1973), 372–378.

Digital Library

[19]

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-Ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. 2022. Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’22). 1342–1355.

[20]

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. 2022. Shortest reconfiguration of perfect matchings via alternating cycles. SIAM J. Discr. Math. 36, 2 (2022), 1102–1123.

Digital Library

[21]

Satoru Iwata and Yusuke Kobayashi. 2010. An algorithm for minimum cost arc-connectivity orientations. Algorithmica 56, 4 (2010), 437–447.

[22]

Tibor Jordán. 2005. On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs. J. Combin. Theory Ser. B 95, 2 (2005), 257–262.

Digital Library

[23]

Zoltán Király and Zoltán Szigeti. 2006. Simultaneous well-balanced orientations of graphs. J. Combin. Theory Ser. B 96, 5 (2006), 684–692.

Digital Library

[24]

László Kozma and Shay Moran. 2013. Shattering, graph orientations, and connectivity. Electr. J. Combin. 20, P44, 3 (2013), 1–18.

[25]

László Lovász. 1993. Combinatorial Problems and Exercises (2nd ed.). North-Holland.

[26]

C. L. Lucchesi and D. H. Younger. 1978. A minimax theorem for directed graphs. J. Lond. Math. Soc. s2–17, 3 (1978), 369–374.

[27]

Hiroshi Nagamochi and Toshihide Ibaraki. 1997. Deterministic \(\tilde{O}\) \((nm)\) time edge-splitting in undirected graphs. J. Combin. Optim. 1, 1 (1997), 5–46.

[28]

C. St. J. A. Nash-Williams. 1960. On orientations, connectivity and odd-vertex-pairings in finite graphs. Can. J. Math. 12 (1960), 555–567.

[29]

H. E. Robbins. 1939. A theorem on graphs, with an application to a problem of traffic control. Am. Math. Month. 46, 5 (1939), 281–283.

[30]

Carsten Thomassen. 1989. Configurations in graphs of large minimum degree, connectivity, or chromatic number. Ann. N. Y. Acad. Sci. 555, 1 (1989), 402–412. arXiv:https://nyaspubs.onlinelibrary.wiley.com/doi/pdf/10.1111/j.1749-6632.1989.tb22479.x.

[31]

Carsten Thomassen. 2015. Strongly 2-connected orientations of graphs. J. Combin. Theory Ser. B 110 (2015), 67–78.

Digital Library

Cited By

来嶋秀(2024)コンピュテーション研究会近況報告IEICE INFORMATION AND SYSTEMS SOCIETY JOURNAL10.1587/ieiceissjournal.29.1_429:1(4-5)Online publication date: 1-May-2024
https://doi.org/10.1587/ieiceissjournal.29.1_4
Hoppenot PSzigeti Z(2024)On reversing arcs to improve arc-connectivityInformation Processing Letters10.1016/j.ipl.2023.106434184(106434)Online publication date: Feb-2024
https://doi.org/10.1016/j.ipl.2023.106434
Abdi ACornuéjols GZambelli G(2024)Arc Connectivity and Submodular Flows in DigraphsCombinatorica10.1007/s00493-024-00108-0Online publication date: 28-May-2024
https://doi.org/10.1007/s00493-024-00108-0

Index Terms

Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Network optimization

Recommendations

The k-Restricted Edge Connectivity of Balanced Bipartite Graphs

For a connected graph G = (V, E), an edge set $${S\subset E}$$ is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ_k(G), is defined ...
A bound on 4-restricted edge connectivity of graphs

An edge cut of a connected graph is 4-restricted if it disconnects this graph with each component having order at least four. The size of minimum 4-restricted edge cuts of graph G is called its 4-restricted edge connectivity and is denoted by @l"4(G). ...
Collapsible subgraphs of a 4-edge-connected graph
Abstract
Jaeger in 1979 showed that every 4-edge-connected graph is supereulerian, graphs that have spanning eulerian subgraphs. Catlin in 1988 sharpened Jaeger’s result by showing that every 4-edge-connected graph is collapsible, graphs that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 19, Issue 1

January 2023

254 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3582898

Editor:
Edith Cohen
Google Research, USA and Tel Aviv University, Israel

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 February 2023

Online AM: 06 September 2022

Accepted: 30 August 2022

Revised: 29 August 2022

Received: 08 April 2022

Published in TALG Volume 19, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

JSPS KAKENHI Grant

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
286
Total Downloads

Downloads (Last 12 months)129
Downloads (Last 6 weeks)22

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

来嶋秀(2024)コンピュテーション研究会近況報告IEICE INFORMATION AND SYSTEMS SOCIETY JOURNAL10.1587/ieiceissjournal.29.1_429:1(4-5)Online publication date: 1-May-2024
https://doi.org/10.1587/ieiceissjournal.29.1_4
Hoppenot PSzigeti Z(2024)On reversing arcs to improve arc-connectivityInformation Processing Letters10.1016/j.ipl.2023.106434184(106434)Online publication date: Feb-2024
https://doi.org/10.1016/j.ipl.2023.106434
Abdi ACornuéjols GZambelli G(2024)Arc Connectivity and Submodular Flows in DigraphsCombinatorica10.1007/s00493-024-00108-0Online publication date: 28-May-2024
https://doi.org/10.1007/s00493-024-00108-0

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents