Abstract
Let G=(V,E) be an undirected graph, and let B ⊆ V ×V be a collection of vertex pairs. We give an incremental polynomial time algorithm to enumerate all minimal edge sets X ⊆ E such that every vertex pair (s,t) ∈ B is disconnected in \((V,E \smallsetminus X)\), generalizing well-known efficient algorithms for enumerating all minimal s-t cuts, for a given pair s,t ∈ V of vertices. We also present an incremental polynomial time algorithm for enumerating all minimal subsets X ⊆ E such that no (s,t) ∈ B is a bridge in (V,X ∪ B). These two enumeration problems are special cases of the more general cut conjunction problem in matroids: given a matroid M on ground set S=E ∪ B, enumerate all minimal subsets X ⊆ E such that no element b ∈ B is spanned by \(E \smallsetminus X\). Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (V,E ∪ B), the enumeration of cut conjunctions for vectorial matroids turns out to be NP-hard.
This research was partially supported by the National Science Foundation (Grant IIS-0118635), and by DIMACS, the National Science Foundation’s Center for Discrete Mathematics and Theoretical Computer Science.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boros, E., Borys, K., Elbassioni, K., Gurvich, V., Khachiyan, L., Makino, K.: Enumerating cut conjunctions in graphs and related problems. Rutcor Research Report RRR 19-2005, Rutgers University
Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L., Makino, K.: Generating paths and cuts in multi-pole (di)graphs. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 298–309. Springer, Heidelberg (2004)
Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L., Makino, K.: On the complexity of some enumeration problems for matroids. To appear in SIAM Journal on Discrete Mathematics (2005)
Eiter, T., Gottlob, G.: Identifyig the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing 24, 1278–1304 (1995)
Fredman, M., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms 21, 618–628 (1996)
Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM Journal on Computing 9, 558–565 (1980)
Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)
Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5, 237–252 (1975)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. B, p. 654. Springer, Heidelberg (2003)
Tsukiyama, S., Shirakawa, I., Ozaki, H., Ariyoshi, H.: An algorithm to enumerate all cutsets of a graph in linear time per cutset. Journal of the Association for Computing Machinery 27, 619–632 (1980)
Vazirani, V.: Approximation Algorithms. Springer, Heidelberg (2001)
Welsh, D.J.A.: Matroid Theory. Academic Press, London (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V., Makino, K. (2005). Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_17
Download citation
DOI: https://doi.org/10.1007/11602613_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30935-2
Online ISBN: 978-3-540-32426-3
eBook Packages: Computer ScienceComputer Science (R0)