×

Htd - a free, open-source framework for (customized) tree decompositions and beyond. (English) Zbl 06756600

Salvagnin, Domenico (ed.) et al., Integration of AI and OR techniques in constraint programming. 14th international conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10335, 376-386 (2017).
Summary: Decompositions of graphs play a central role in the field of parameterized complexity and are the basis for many fixed-parameter tractable algorithms for problems that are NP-hard in general. Tree decompositions are the most prominent concept in this context and several tools for computing tree decompositions recently competed in the 1st Parameterized Algorithms and Computational Experiments Challenge. However, in practice the quality of a tree decomposition cannot be judged without taking concrete algorithms that make use of tree decompositions into account. In fact, practical experience has shown that generating decompositions of small width is not the only crucial ingredient towards efficiency. To this end, we present htd, a free and open-source software library, which includes efficient implementations of several heuristic approaches for tree decomposition and offers various features for normalization and customization of decompositions. The aim of this article is to present the specifics of htd together with an experimental evaluation underlining the effectiveness and efficiency of the implementation.
For the entire collection see [Zbl 1364.68017].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Abseher, M.: htd 1.0.0-beta1 (2016). http://github.com/mabseher/htd/tree/v1.0.0-beta1
[2] Abseher, M., Bliem, B., Charwat, G., Dusberger, F., Hecher, M., Woltran, S.: The D-FLAT system for dynamic programming on tree decompositions. In: Fermé, E., Leite, J. (eds.) JELIA 2014. LNCS, vol. 8761, pp. 558–572. Springer, Cham (2014). doi: 10.1007/978-3-319-11558-0_39 · Zbl 1432.68053
[3] Abseher, M., Bliem, B., Charwat, G., Dusberger, F., Hecher, M., Woltran, S.: D-FLAT: progress report. Technical report, DBAI-TR-2014-86, TU Wien (2014). http://www.dbai.tuwien.ac.at/research/report/dbai-tr-2014-86.pdf · Zbl 1432.68053
[4] Abseher, M., Dusberger, F., Musliu, N., Woltran, S.: Improving the efficiency of dynamic programming on tree decompositions via machine learning. In: Proceedings of IJCAI, pp. 275–282. AAAI Press (2015)
[5] Abseher, M., Musliu, N., Woltran, S.: htd - A free, open-source framework for tree decompositions and beyond. Technical report, DBAI-TR-2016-96, TU Wien (2016). http://www.dbai.tuwien.ac.at/research/report/dbai-tr-2016-96.pdf · Zbl 06756600
[6] Abseher, M., Musliu, N., Woltran, S.: Improving the efficiency of dynamic programming on tree decompositions via machine learning. Technical report, DBAI-TR-2016-94, TU Wien (2016). http://www.dbai.tuwien.ac.at/research/report/dbai-tr-2016-94.pdf · Zbl 1407.68386
[7] Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a \[ k \]
-tree. J. Algebraic Discrete Methods 8(2), 277–284 (1987) · Zbl 0611.05022
[8] Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial \[ k \]
-trees. Discrete Appl. Math. 23(1), 11–24 (1989) · Zbl 0666.68067
[9] Bachoore, E.H., Bodlaender, H.L.: A branch and bound algorithm for exact, upper, and lower bounds on treewidth. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol. 4041, pp. 255–266. Springer, Heidelberg (2006). doi: 10.1007/11775096_24 · Zbl 1137.68465
[10] Berry, A., Heggernes, P., Simonet, G.: The minimum degree heuristic and the minimal triangulation process. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 58–70. Springer, Heidelberg (2003). doi: 10.1007/978-3-540-39890-5_6 · Zbl 1255.05186
[11] Bertelè, U., Brioschi, F.: On non-serial dynamic programming. J. Comb. Theor. Ser. A 14(2), 137–148 (1973) · Zbl 0264.49021
[12] Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255–269 (2008) · Zbl 05534220
[13] Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Inf. Comput. 208(3), 259–275 (2010) · Zbl 1186.68328
[14] Charwat, G., Woltran, S.: Dynamic programming-based QBF solving. In: Proceedings of the 4th International Workshop on Quantified Boolean Formulas, vol. 1719, pp. 27–40. CEUR Workshop Proceedings (2016)
[15] Clautiaux, F., Moukrim, A., Négre, S., Carlier, J.: Heuristic and meta-heuristic methods for computing graph treewidth. RAIRO Oper. Res. 38, 13–26 (2004) · Zbl 1092.90065
[16] Dechter, R.: Constraint Processing. Morgan Kaufmann, USA (2003) · Zbl 1057.68114
[17] Dourisboure, Y.: Compact routing schemes for generalised chordal graphs. J. Graph Algorithms Appl. 9(2), 277–297 (2005)
[18] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)
[19] Ganzow, T., Gottlob, G., Musliu, N., Samer, M.: A CSP hypergraph library. Technical report, DBAI-TR-2005-50, TU Wien (2005). http://www.dbai.tuwien.ac.at/proj/hypertree/csphgl.pdf
[20] Gaspers, S., Gudmundsson, J., Jones, M., Mestre, J., Rümmele, S.: Turbocharging treewidth heuristics. In: Proceedings of IPEC (2016, to appear) · Zbl 1398.68490
[21] Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. In: Proceedings of UAI, pp. 201–208. AUAI Press (2004)
[22] Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. 64(3), 579–627 (2002) · Zbl 1052.68025
[23] Halin, R.: S-functions for graphs. J. Geom. 8, 171–186 (1976) · Zbl 0339.05108
[24] Hamann, M., Strasser, B.: Graph bisection with pareto-optimization. In: Proceedings of ALENEX, pp. 90–102. SIAM (2016) · Zbl 1414.68141
[25] Hammerl, T., Musliu, N.: Ant colony optimization for tree decompositions. In: Cowling, P., Merz, P. (eds.) EvoCOP 2010. LNCS, vol. 6022, pp. 95–106. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-12139-5_9 · Zbl 05694674
[26] Hammerl, T., Musliu, N., Schafhauser, W.: Metaheuristic algorithms and tree decomposition. In: Kacprzyk, J., Pedrycz, W. (eds.) Springer Handbook of Computational Intelligence, pp. 1255–1270. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-43505-2_64
[27] Jégou, P., Terrioux, C.: Bag-connected tree-width: a new parameter for graph decomposition. In: Proceedings of ISAIM, pp. 12–28 (2014)
[28] Kjaerulff, U.: Optimal decomposition of probabilistic networks by simulated annealing. Stat. Comput. 2(1), 2–17 (1992)
[29] Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994) · Zbl 0825.68144
[30] Koster, A.M.C.A., van Hoesel, S.P.M., Kolen, A.W.J.: Solving frequency assignment problems via tree-decomposition 1. Electr. Notes Discrete Math. 3, 102–105 (1999) · Zbl 1038.90086
[31] Larranaga, P., Kujipers, C.M., Poza, M., Murga, R.H.: Decomposing bayesian networks: triangulation of the moral graph with genetic algorithms. Stat. Comput. 7(1), 19–34 (1997)
[32] Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. J. R. Stat. Soc. Ser. B 50, 157–224 (1988) · Zbl 0684.68106
[33] Morak, M., Musliu, N., Pichler, R., Rümmele, S., Woltran, S.: Evaluating tree-decomposition based algorithms for answer set programming. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, pp. 130–144. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-34413-8_10 · Zbl 06105733
[34] Musliu, N.: An iterative heuristic algorithm for tree decomposition. In: Cotta, C., van Hemert, J. (eds.) Recent Advances in Evolutionary Computation for Combinatorial Optimization. Studies in Computational Intelligence, vol. 153, pp. 133–150. Springer, Heidelberg (2008) · Zbl 1159.90499
[35] Musliu, N., Schafhauser, W.: Genetic algorithms for generalized hypertree decompositions. Eur. J. Ind. Eng. 1(3), 317–340 (2007)
[36] Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)
[37] Robertson, N., Seymour, P.: Graph minors. III. Planar tree-width. J. Comb. Theor. Ser. B 36(1), 49–64 (1984) · Zbl 0548.05025
[38] Robertson, N., Seymour, P.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theor. Ser. B 52(2), 153–190 (1991) · Zbl 0764.05069
[39] Shoikhet, K., Geiger, D.: A practical algorithm for finding optimal triangulations. In: Proceedings of AAAI/IAAI, pp. 185–190. AAAI Press/The MIT Press (1997)
[40] Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithm to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 566–579 (1984) · Zbl 0545.68062
[41] van Wersch, R., Kelk, S.: Toto: an open database for computation, storage and retrieval of tree decompositions. Discrete Appl. Math. 217, 389–393 (2017) · Zbl 1358.05002
[42] Xu, J., Jiao, F., Berger, B.: A tree-decomposition approach to protein structure prediction. In: Proceedings of CSB, pp. 247–256 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.