Abstract
The well-known Courcelle’s theorem states that many graph properties (that are expressible in monadic second order logic) can be solved in linear time on graphs of bounded treewidth. Logspace versions of this using automata theoretic framework are also known. In this paper, we develop an alternate methodology using the standard table-based dynamic programming approach to give a space efficient version of Courcelle’s theorem. We assume that the given graph and its tree decomposition are given in a read-only memory. Our algorithms use the recently developed stack-compression machinery and the classical framework of Borie et al. to develop time-space tradeoffs for dynamic programming algorithms that use \({\mathcal {O}}(p \log _p n)\) variables where \(2 \le p \le n\) is a parameter. En route we also generalize the stack compression framework to a broader class of algorithms, which we believe can be of independent interest.
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
Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. Journal of Algorithms 12, 308–340 (1991)
Asano, T.: Constant-Working-Space Algorithms for Image Processing. In: Nielsen, F. (ed.) ETVC 2008. LNCS, vol. 5416, pp. 268–283. Springer, Heidelberg (2009)
Asano, T.: Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array? In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 1–1. Springer, Heidelberg (2008)
Asano, T.: Designing Algorithms with Limited Work Space. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol. 6648, pp. 1–1. Springer, Heidelberg (2011)
Asano, T., Doerr, B.: Memory-constrained algorithms for shortest path problem. In: Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, CCCG (2011)
Asano, T., Kirkpatrick, D., Nakagawa, K., Watanabe, O.: \(\widetilde{O}(\sqrt{n})\)-Space and polynomial-time algorithm for planar directed graph reachability. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 45–56. Springer, Heidelberg (2014)
Asano, T., Mulzer, W., Rote, G., Wang, Y.: Constant-work-space algorithms for geometric problems. JoCG 2(1), 46–68 (2011)
Asano, T., Mulzer, W., Wang, Y.: Constant-work-space algorithms for shortest paths in trees and simple polygons. J. Graph Algorithms Appl. 15(5), 569–586 (2011)
Aspvall, B., Telle, J.A., Proskurowski, A.: Memory requirements for table computations in partial k-tree algorithms. Algorithmica 27(3), 382–394 (2000)
Barba, L., Korman, M., Langerman, S., Sadakane, K., Silveira, R.: Space-time trade-offs for stack-based algorithms. Algorithmica (2014) (in press)
Bhattacharya, B.K., De, M., Nandy, S.C., Roy, S.: Maximum independent set for interval graphs and trees in space efficient models. In: Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG (2014)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1–2), 1–45 (1998)
Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255–269 (2008)
Bodlaende, H.L., Telle, J.A.: Space-efficient construction variants of dynamic programming. Nord. J. Comput. 11(4), 374–385 (2004)
Borie, R.B.: Gary Parker, R., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7(5&6), 555–581 (1992)
Bose, P., Morin, P.: An improved algorithm for subdivision traversal without extra storage. Int. J. Comput. Geometry Appl. 12(4), 297–308 (2002)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)
Courcelle, B.: The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Inform. and Comput. 85, 12–75 (1990)
Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1, pp. 313–400. World Sci. Publ., River Edge (1997)
Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. Cambridge University Press (2012)
Datta, S., Limaye, N., Nimbhorkar, P., Thierauf, T., Wagner, F.: Planar graph isomorphism is in log-space. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, pp. 203–214 (2009)
De, M., Nandy, S.C., Roy, S.: Convex hull and linear programming in read-only setup with limited work-space. CoRR, abs/1212.5353 (2012)
Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of bodlaender and courcelle. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, pp. 143–152 (2010)
Grohe, M., Marx, D.: Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput. 44(1), 114–159 (2015)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)
Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17:1–17:24 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Banerjee, N., Chakraborty, S., Raman, V., Roy, S., Saurabh, S. (2015). Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs. In: Xu, D., Du, D., Du, D. (eds) Computing and Combinatorics. COCOON 2015. Lecture Notes in Computer Science(), vol 9198. Springer, Cham. https://doi.org/10.1007/978-3-319-21398-9_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-21398-9_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21397-2
Online ISBN: 978-3-319-21398-9
eBook Packages: Computer ScienceComputer Science (R0)