nach oben

Theory of Computing Systems

Erschienen in:

09.03.2017

Space Saving by Dynamic Algebraization Based on Tree-Depth

verfasst von: Martin Fürer, Huiwen Yu

Erschienen in: Theory of Computing Systems | Ausgabe 2/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithms based on tree decompositions in polynomial space. We show how to use a tree decomposition and extend the algebraic techniques of Lokshtanov and Nederlof (In: 42nd ACM Symposium on Theory of Computing, pp. 321–330, 2010) such that a typical dynamic programming algorithm runs in time O ^∗(2^h), where h is the tree-depth (Nešetřil et al., Eur. J. Comb. 27(6):1022–1041, 2006) of a graph. In general, we assume that a tree decomposition of depth h is given. We apply our algorithm to the problem of counting perfect matchings on grids and show that it outperforms other polynomial-space solutions. We also apply the algorithm to other set covering and partitioning problems.

Vorheriger Artikel The Connectivity of Boolean Satisfiability: Dichotomies for Formulas and Circuits

Nächster Artikel The Query Complexity of Witness Finding

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

O ^∗ notation hides the polynomial factors of the expression.

Amir, E.: Efficient Approximation for Triangulation of Minimum Treewidth Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, pp 7–15 (2001)

Amir, E.: Approximation algorithms for treewidth. Algorithmica 56(4), 448–479 (2010). doi:10.1007/s00453-008-9180-4 MathSciNetCrossRefMATH

Björklund, A.: Counting Perfect Matchings as Fast as Ryser 23Rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp 914–921 (2012)CrossRef

Björklund, A., Husfeldt, T.: Exact algorithms for exact satisfiability and number of perfect matchings. Algorithmica 52(2), 226–249 (2008)MathSciNetCrossRefMATH

Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier Meets Möbius: Fast Subset Convolution 39Th Annual ACM Symposium on Theory of Computing, pp 67–74 (2007)

Bodlaender, H.L.: Dynamic Programming on Graphs with Bounded Treewidth 15Th International Colloquium on Automata, Languages and Programming, pp 105–118 (1988)CrossRef

Bodlaender, H.L.: NC-Algorithms for Graphs with Small Treewidth 14Th International Workshop on Graph-Theoretic Concepts in Computer Science, pp 1–10 (1989)

Bodlaender, H.L.: A Linear Time Algorithm for Finding Tree-Decompositions of Small Treewidth 25Th Annual ACM Symposium on Theory of Computing, pp 226–234 (1993)

Bodlaender, H.L.: Discovering Treewidth 31St Conference on Current Trends in Theory and Practice of Computer Science, pp 1–16 (2005)

10.

Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: An O(C ^k N) 5-Approximation Algorithm for Treewidth 54Th Annual IEEE Symposium on Foundations of Computer Science, pp 499–508 (2013)

11.

Bodlaender, H.L., Gilbert, J.R., Kloks, T., Hafsteinsson, H.: Approximating Treewidth, Pathwidth, and Minimum Elimination Tree Height 17Th International Workshop on Graph-Theoretic Concepts in Computer Science, pp 1–12 (1992)

12.

Bouchitté, V., Kratsch, D., Müller, H., Todinca, I.: On treewidth approximations. Discrete Appl. Math. 136(2-3), 183–196 (2004)MathSciNetCrossRefMATH

13.

Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J. M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time 52nd Annual IEEE Symposium on Foundations of Computer Science, pp 150–159 (2011)

14.

Feige, U., Hajiaghayi, M., Lee, J.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38(2), 629–657 (2008). doi:10.1137/05064299X MathSciNetCrossRefMATH

15.

Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181–207 (2009)MathSciNetCrossRefMATH

16.

Fürer, M.: Faster integer multiplication. SIAM J. Comput. 39(3), 979–1005 (2009)MathSciNetCrossRefMATH

17.

Gottlob, G., Leone, N., Scarcello, F.: Hypertree Decompositions: a Survey Mathematical Foundations of Computer Science, pp 37–57 (2001)

18.

Kenyon, C., Randall, D., Sinclair, A.: Approximating the number of monomer-dimer coverings of a lattice. J. Stat. Phys. 83(3), 637–659 (1996). doi:10.1007/BF02183743

19.

Kloks, T.: Treewidth, Computations and Approximations, vol. 842. Springer (1994)

20.

Kneis, J., Mölle, D., Richter, S., Rossmanith, P.: A bound on the pathwidth of sparse graphs with applications to exact algorithms. SIAM J. Discret. Math. 23(1), 407–427 (2009)MathSciNetCrossRefMATH

21.

Koutis, I.: Faster Algebraic Algorithms for Path and Packing Problems 35Th International Colloquium on Automata, Languages and Programming, pp 575–586 (2008)

22.

Koutis, I., Williams, R.: Limits and Applications of Group Algebras for Parameterized Problems 36Th International Colloquium on Automata, Languages and Programming, pp 653–664 (2009)

23.

Lokshtanov, D., Mnich, M., Saurabh, S.: Planar K-Path in Subexponential Time and Polynomial Space 37Th International Workshop on Graph-Theoretic Concepts in Computer Science, pp 262–270 (2011)

24.

Lokshtanov, D., Nederlof, J.: Saving Space by Algebraization. In: 42nd ACM Symposium on Theory of Computing, pp 321–330 (2010)

25.

Miller, G.L., Teng, S.H., Thurston, W., Vavasis, S.A.: Separators for sphere-packings and nearest neighbor graphs. J. ACM 44(1), 1–29 (1997)MathSciNetCrossRefMATH

26.

Nederlof, J.: Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65(4), 868–884 (2013)MathSciNetCrossRefMATH

27.

Nešetřil, J., de Mendez, P.O.: Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb. 27(6), 1022–1041 (2006)

28.

van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution 17Th Annual European Symposium on Algorithms, pp 566–577 (2009)

29.

van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion/Exclusion Meets Measure and Conquer 17Th Annual European Symposium on Algorithms, pp 554–565 (2009)

30.

Rota, G.C.: On the foundations of combinatorial theory. i. theory of möbius functions. Zeitschrift fü,r Wahrscheinlichkeitstheorie und Verwandte Gebiete 2(4), 340–368 (1964)CrossRefMATH

31.

Stanley, R., Rota, G.: Enumerative Combinatorics, vol. 1. Cambridge University Press (2000)

32.

Temperley, H., Fisher, M.: Dimer problem in statistical mechanics - an exact result. Philos. Mag. 6, 1061–1063 (1961)MathSciNetCrossRefMATH

33.

Woeginger, G.J.: Space and Time Complexity of Exact Algorithms: Some Open Problems (Invited Talk) 1St International Workshop on Parameterized and Exact Computation, pp 281–290 (2004)

Titel: Space Saving by Dynamic Algebraization Based on Tree-Depth
verfasst von: Martin Fürer
Huiwen Yu
Publikationsdatum: 09.03.2017
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 2/2017
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-017-9751-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2017

Separation Logic with One Quantified Variable

Guest Editorial: Computer Science Symposium in Russia

Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts

Satisfiability of ECTL∗ with Local Tree Constraints

Optimizing Binary Heaps

The Query Complexity of Witness Finding