research-article
Authors: Alice Raffaele, Romeo Rizzi, and Takeaki Uno
Published: 02 July 2024 Publication History
- 0citation
- 0
- Downloads
Metrics
Total Citations0Total Downloads0Last 12 Months0
Last 6 weeks0
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
- View Options
- References
- Media
- Tables
- Share
Abstract
Given a connected graph G = ( V, E ), with n ≔ | V | vertices and m ≔ | E | edges, a cut can be represented as a bipartition { S, S ¯ } of the vertices or as the set of those edges in E having one endpoint in S and the other in S ¯, denoted by δ G ( S, S ¯ ). A cut is minimal, or also called bond, if and only if the two induced subgraphs obtained by removing the edges in the cut are both connected. When the bond separates two given vertices s and t, we talk about s, t-bond. In this work, we consider the problems of listing all the bonds and listing all the s, t-bonds in a graph. These fundamental problems find application in many research areas, such as, beyond graph theory, network reliability, bioinformatics, and chemistry. The state-of-the-art algorithm exploits binary partition to output each s, t-bond in O ( m ) per bond, being thus classified as an O ( m )-delay algorithm. Here we present two new algorithms to address these problems. The first one implements a slightly different branching strategy than the state of the art, though achieving the same complexity. Anyway, we can improve it by relying on dynamic data structures and amortized analysis, obtaining an algorithm that outputs a new bond in O ˜ ( n ). By assuming only the two bond-shores are output for every bond, this is the first output-linear algorithm listing bonds. In case we commit to explicitly providing the entire edge-set of every bond, the delay becomes O ˜ ( n ) + | δ G ( S, S ¯ ) |.
Highlights
•
We study the problem of listing all minimal cuts (or bonds) in a graph.
•
We exploit a different branching strategy than Tsukiyama et al. (1980).
•
We provide a first algorithm having the same complexity as Tsukiyama et al. (1980).
•
We rely on dynamic data structures and amortized analysis to improve our approach.
•
We propose the first O ˜ ( n )-delay algorithm to list all bonds in a graph.
References
[1]
Abel U., Bicker R., Determination of all minimal cut-sets between a vertex pair in an undirected graph, IEEE Trans. Reliab. R-31 (2) (1982) 167–171,.
[2]
Alstrup S., Holm J., deLichtenberg K., Thorup M., Minimizing diameters of dynamic trees, in: Degano P., Gorrieri R., Marchetti-Spaccamela A. (Eds.), Automata, Languages and Programming, Springer Berlin Heidelberg, Berlin, Heidelberg, 1997, pp. 270–280.
[3]
Alstrup S., Holm J., Lichtenberg K.D., Thorup M., Maintaining information in fully dynamic trees with top trees, ACM Trans. Algorithms 1 (2) (2005) 243–264,.
Digital Library
[4]
Apaolaza I., San José-Eneriz E., Tobalina L., Miranda E., Garate L., Agirre X., Prósper F., Planes F.J., An in-silico approach to predict and exploit synthetic lethality in cancer metabolism, Nature Commun. 8 (1) (2017) 1–9.
[5]
Arunkumar S., Lee S.H., Enumeration of all minimal cut-sets for a node pair in a graph, IEEE Trans. Reliab. R-28 (1) (1979) 51–55,.
[6]
Bellmore M., Jensen P.A., An implicit enumeration scheme for proper cut generation, Technometrics 12 (4) (1970) 775–788,. arXiv:https://www.tandfonline.com/doi/pdf/10.1080/00401706.1970.10488728. URL https://www.tandfonline.com/doi/abs/10.1080/00401706.1970.10488728.
[7]
Bondy J.A., Murty U., Graph Theory with Applications, Macmillan, 1976, URL https://books.google.it/books?id=jCqUswEACAAJ.
Digital Library
[8]
Cheliyan A., Bhattacharyya S., Fuzzy fault tree analysis of oil and gas leakage in subsea production systems, J. Ocean Eng. Sci. 3 (1) (2018) 38–48,. URL https://www.sciencedirect.com/science/article/pii/S2468013317300591.
[9]
Colbourn C.J., The Combinatorics of Network Reliability, Oxford University Press Inc., USA, 1987.
Digital Library
[10]
Conte A., Grossi R., Marino A., Rizzi R., Uno T., Versari L., Tight lower bounds for the number of inclusion-minimal st-cuts, in: Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, 2018, pp. 100–110,.
Digital Library
[11]
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms, third ed., The MIT Press, 2009.
[12]
Debieux V., Pignolet Y., Sivanthi T., Faster exact reliability computation, in: 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops, DSN-W, 2017, pp. 121–124,.
[13]
Deo N., Graph Theory with Applications To Engineering and Computer Science, Dover Publications, 2017, URL https://books.google.it/books?id=DSBMDgAAQBAJ.
Digital Library
[14]
Diestel R., Graph Theory, fifth ed., Springer Publishing Company, Incorporated, 2017.
[15]
Duarte G.L., Eto H., Hanaka T., Kobayashi Y., Kobayashi Y., Lokshtanov D., Pedrosa L.L.C., Schouery R.C.S., Souza U.S., Computing the largest bond and the maximum connected cut of a graph, Algorithmica 83 (5) (2021) 1421–1458,.
Digital Library
[16]
Eppstein D., Löffler M., Strash D., Listing all maximal cliques in sparse graphs in near-optimal time, in: Cheong O., Chwa K.Y., Park K. (Eds.), Algorithms and Computation, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010, pp. 403–414.
[17]
Eppstein D., Strash D., Listing all maximal cliques in large sparse real-world graphs, in: Pardalos P.M., Rebennack S. (Eds.), Experimental Algorithms, Springer Berlin Heidelberg, Berlin, Heidelberg, 2011, pp. 364–375.
[18]
Eriksson A.P., Barr O., Astrom K., Image segmentation using minimal graph cuts, in: SSBA Symposium on Image Analysis, 2006, URL https://eprints.qut.edu.au/108194/.
[19]
Frederickson G.N., Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees, SIAM J. Comput. 26 (2) (1997) 484–538,.
Digital Library
[20]
Gaur V., Yadav O.P., Soni G., Rathore A.P.S., A literature review on network reliability analysis and its engineering applications, Proc. Inst. Mech. Eng., Part O: J. Risk Reliab. 235 (2) (2021) 167–181,.
[21]
Gerstl M.P., Klamt S., Jungreuthmayer C., Zanghellini J., Exact quantification of cellular robustness in genome-scale metabolic networks, Bioinformatics 32 (5) (2016) 730–737.
[22]
Grossi R., Enumeration of paths, cycles, and spanning trees, in: Encyclopedia of Algorithms, Springer New York, New York, NY, 2016, pp. 640–645,.
[23]
Hädicke O., Klamt S., Computing complex metabolic intervention strategies using constrained minimal cut sets, Metabolic Eng. 13 (2010) 204–213,.
[24]
Harary F., Graph Theory, Addison-Wesley, Reading, MA, 1969.
[25]
Henzinger M.R., Fredman M.L., Lower bounds for fully dynamic connectivity problems in graphs, Algorithmica 22 (3) (1998) 351–362.
[26]
Henzinger M.R., King V., Randomized fully dynamic graph algorithms with polylogarithmic time per operation, J. ACM 46 (4) (1999) 502–516.
[27]
Holm J., deLichtenberg K., Thorup M., Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, J. ACM 48 (4) (2001) 723–760,.
Digital Library
[28]
Hopcroft J.E., Tarjan R.E., Algorithm 447: Efficient algorithms for graph manipulation, Commun. ACM 16 (6) (1973) 372–378,. URL http://doi.acm.org/10.1145/362248.362272.
Digital Library
[29]
Jensen P.A., Bellmore M., An algorithm to determine the reliability of a complex system, IEEE Trans. Rehahty R-I 4 (1969) 169–174.
[30]
Jung S., Yoo J., Lee Y.J., A software fault tree analysis technique for formal requirement specifications of nuclear reactor protection systems, Reliab. Eng. Syst. Saf. 203 (2020),. URL https://www.sciencedirect.com/science/article/pii/S0951832020305652.
[31]
Kao M.Y. (Ed.), Encyclopedia of Algorithms, second ed., Springer, New York, 2016,.
[32]
Kiyomi M., Reverse search; enumeration algorithms, in: Encyclopedia of Algorithms, Springer New York, New York, NY, 2016, pp. 1840–1842,.
[33]
Klamt S., Gilles E.D., Minimal cut sets in biochemical reaction networks, Bioinformatics 20 2 (2004) 226–234.
[34]
Lin H.-Y., Kuo S.-Y., Yeh F.-M., Minimal cutset enumeration and network reliability evaluation by recursive merge and BDD, in: Proceedings of the Eighth IEEE Symposium on Computers and Communications, ISCC 2003, 2003, pp. 1341–1346,.
[35]
Liu C.L., Edelberg M., Introduction to Combinatorial Mathematics, in: Computer science series, McGraw-Hill, 1968, URL https://books.google.it/books?id=Dr8-AAAAIAAJ.
[36]
Martelli A., A Gaussian elimination algorithm for the enumeration of cut sets in a graph, J. ACM 23 (1) (1976) 58–73,.
Digital Library
[37]
Miltersen P.B., Subramanian S., Vitter J.S., Tamassia R., Complexity models for incremental computation, Theoret. Comput. Sci. 130 (1) (1994) 203–236,. URL http://www.sciencedirect.com/science/article/pii/0304397594901597.
Digital Library
[38]
Nguyen T.P., Lin Y.K., Reliability assessment of a stochastic air transport network with late arrivals, Comput. Ind. Eng. 151 (2021),. URL https://www.sciencedirect.com/science/article/pii/S0360835220306318.
[39]
Niu Y.F., Gao Z.Y., Lam W.H., Evaluating the reliability of a stochastic distribution network in terms of minimal cuts, Transp. Res. Part E: Logist. Transp. Rev. 100 (2017) 75–97,. URL https://www.sciencedirect.com/science/article/pii/S1366554516306354.
[40]
Peng B., Zhang L., Zhang D., A survey of graph theoretical approaches to image segmentation, Pattern Recognit. 46 (3) (2013) 1020–1038,. URL https://www.sciencedirect.com/science/article/pii/S0031320312004219.
Digital Library
[41]
Schaefer T.J., The complexity of satisfiability problems, in: Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978), ACM, New York, 1978, pp. 216–226. 521057.
[42]
Shier D.R., Network Reliability and Algebraic Structures, Clarendon Press, USA, 1991.
[43]
Sleator D.D., Tarjan R.E., A data structure for dynamic trees, J. Comput. System Sci. 26 (1983) 362–391.
[44]
Tarjan R., Depth-first search and linear graph algorithms, in: 12th Annual Symposium on Switching and Automata Theory, Swat 1971, 1971, pp. 114–121,.
Digital Library
[45]
Thorup M., Near-optimal fully-dynamic graph connectivity, in: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, in: STOC ’00, Association for Computing Machinery, New York, NY, USA, 2000, pp. 343–350,.
Digital Library
[46]
Tsukiyama S., Shirakawa I., Ozaki H., Ariyoshi H., An algorithm to enumerate all cutsets of a graph in linear time per cutset, J. ACM 27 (1980) 619–632.
[47]
Tutte W.T., Connectivity in Graphs, in: Mathematical expositions, University of Toronto Press, 1966, URL https://books.google.it/books?id=lppsAAAAMAAJ.
[48]
Uno T., Amortized analysis on enumeration algorithms, in: Encyclopedia of Algorithms, Springer New York, New York, NY, 2016, pp. 72–76,.
[49]
VanSlyke R.M., Frank H., Network reliability analysis: Part i, Networks 1 (3) (1971) 279–290,. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.3230010307. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230010307.
[50]
Wasa K., Enumeration of enumeration algorithms and its complexity, 2019, https://kunihirowasa.github.io/enum. (Accessed 28 February 2020).
[51]
Wilson R., Introduction to Graph Theory, Oliver and Boyd, (Edinburgh) and Academic Press (New York), 1972.
[52]
Wulff-Nilsen C., Faster deterministic fully-dynamic graph connectivity, in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’13, Society for Industrial and Applied Mathematics, USA, 2013, pp. 1757–1769.
[53]
Yan L., Taha H.A., Landers T.L., A recursive approach for enumerating minimal cutsets in a network, IEEE Trans. Reliab. 43 (3) (1994) 383–388,.
Recommendations
- A Linear Delay Algorithm for Enumeration of 2-Edge/Vertex-Connected Induced Subgraphs
Combinatorial Algorithms
Abstract
In this paper, we present the first linear delay algorithms to enumerate all 2-edge-connected induced subgraphs and to enumerate all 2-vertex-connected induced subgraphs for a given simple undirected graph. We treat these subgraph enumeration ...
Read More
- Listing all the minimal separators of a 3-connected planar graph
We present an efficient algorithm that lists the minimal separators of a 3-connected planar graph in O(n) per separator.
Read More
- On the generation of bicliques of a graph
An independent set of a graph is a subset of pairwise non-adjacentvertices. A complete bipartite set B is a subset of verticesadmitting a bipartition B=X∪Y, such that both X and Y areindependent sets, and all vertices of X are adjacent to those of Y.If ...
Read More
Comments
Information & Contributors
Information
Published In
Discrete Applied Mathematics Volume 348, Issue C
May 2024
320 pages
ISSN:0166-218X
Issue’s Table of Contents
Elsevier B.V.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 02 July 2024
Author Tags
- Enumeration
- Graph theory
- Minimal cut
- Binary partition
- Dynamic data structure
- Amortized analysis
Qualifiers
- Research-article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
Total Citations
Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Other Metrics
View Author Metrics
Citations
View Options
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.
Sign in
Full Access
Get this Publication
Media
Figures
Other
Tables
