Abstract
Ordered Binary Decision Diagrams (OBDDs) are a data structure for Boolean functions which is successfully applied in many areas like Integer Programming, Model Checking, and Relational Algebra. Nevertheless, many basic graph problems like Connectivity, Reachability, Single-Source Shortest-Paths, and Flow Maximization are known to be PSPACE-hard if their input graphs are represented by OBDDs. This holds even for input OBDDs of constant width. We extend these results by concrete exponential lower bounds on the space complexity of OBDD-based algorithms for the Reachability Problem, the Single-Source Shortest-Paths Problem, and the Maximum Flow Problem. This involves the first exponential lower bound on the OBDD size for the highest bit of Integer Multiplication w. r. t. the natural interleaved variable order.
An extended version of this paper is available at http://ls2-www.cs.uni-dortmund. de/ sawitzki/.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Becker, B., Behle, M., Eisenbrand, F., Wimmer, R.: BDDs in a branch and cut framework. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 452–463. Springer, Heidelberg (2005)
Berghammer, R., Neumann, F.: RELVIEW - An OBDD-based computer algebra system for relations. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2005. LNCS, vol. 3718, pp. 40–51. Springer, Heidelberg (2005)
Bryant, R.E.: Symbolic manipulation of Boolean functions using a graphical representation. In: DAC 1985, pp. 688–694. ACM Press, New York (1985)
Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers 35, 677–691 (1986)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Feigenbaum, J., Kannan, S., Vardi, M.Y., Viswanathan, M.: Complexity of problems on graphs represented as OBDDs. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 216–226. Springer, Heidelberg (1998)
Gavalda, R., Guijarro, D.: Learning Ordered Binary Decision Diagrams. In: Zeugmann, T., Shinohara, T., Jantke, K.P. (eds.) ALT 1995. LNCS, vol. 997, pp. 228–238. Springer, Heidelberg (1995)
Gentilini, R., Piazza, C., Policriti, A.: Computing strongly connected components in a linear number of symbolic steps. In: SODA 2003, pp. 573–582. ACM Press, New York (2003)
Gentilini, R., Policriti, A.: Biconnectivity on symbolically represented graphs: A linear solution. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 554–564. Springer, Heidelberg (2003)
Hachtel, G.D., Somenzi, F.: Logic Synthesis and Verification Algorithms. Kluwer Academic Publishers, Boston (1996)
Hachtel, G.D., Somenzi, F.: A symbolic algorithm for maximum flow in 0–1 networks. Formal Methods in System Design 10, 207–219 (1997)
Jin, H., Kuehlmann, A., Somenzi, F.: Fine-grain conjunction scheduling for symbolic reachability analysis. In: Katoen, J.-P., Stevens, P. (eds.) TACAS 2002. LNCS, vol. 2280, pp. 312–326. Springer, Heidelberg (2002)
Ravi, K., Bloem, R., Somenzi, F.: A comparative study of symbolic algorithms for the computation of fair cycles. In: Johnson, S.D., Hunt Jr., W.A. (eds.) FMCAD 2000. LNCS, vol. 1954, pp. 143–160. Springer, Heidelberg (2000)
Sawitzki, D.: Implicit flow maximization by iterative squaring. In: Van Emde Boas, P., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 301–313. Springer, Heidelberg (2004)
Sawitzki, D.: A symbolic approach to the all-pairs shortest-paths problem. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 154–167. Springer, Heidelberg (2004)
Sawitzki, D.: Lower bounds on the OBDD size of graphs of some popular functions. In: Vojtáš, P., Bieliková, M., Charron-Bost, B., Sýkora, O. (eds.) SOFSEM 2005. LNCS, vol. 3381, pp. 298–309. Springer, Heidelberg (2005)
Sawitzki, D.: The complexity of problems on implicitly represented inputs. In: To appear in SOFSEM 2006 (2006)
Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM, Philadelphia (2000)
Woelfel, P.: New bounds on the OBDD-size of integer multiplication via universal hashing. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 563–574. Springer, Heidelberg (2001)
Woelfel, P.: Symbolic topological sorting with oBDDs. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 671–680. Springer, Heidelberg (2003)
Xie, A., Beerel, P.A.: Implicit enumeration of strongly connected components. In: ICCAD 1999, pp. 37–40. ACM Press, New York (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sawitzki, D. (2006). Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms. In: Correa, J.R., Hevia, A., Kiwi, M. (eds) LATIN 2006: Theoretical Informatics. LATIN 2006. Lecture Notes in Computer Science, vol 3887. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11682462_71
Download citation
DOI: https://doi.org/10.1007/11682462_71
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32755-4
Online ISBN: 978-3-540-32756-1
eBook Packages: Computer ScienceComputer Science (R0)