On the Relevance of Optimal Tree Decompositions for Constraint Networks

Abstract : For the study and the solving of NP-hard problems, the concept of tree decomposition is nowadays a major topic in Computer Science, in Artificial Intelligence and particularly in Constraint Programming. It appears as a promising field for the theoretical study of numerous graphical models like Bayesian Networks or (Weighted) Constraint Networks, since it can ensure, under some hypothesis, the existence of polynomial time algorithms. This concept is also used in a wide range of applications. Recently, a real improvement in the practical computation of optimal tree decompositions has been observed, allowing new promising applications of this concept in real applications. In this paper, we first aim to analyze the real relevance of such optimal decompositions. We first set that a larger set of instances are now optimally decomposable in practice but using these algorithms on a practical level still constitutes a real difficulty. In a second time, we assess the impact of such optimal decompositions for solving these instances and note a discrepancy between the empirical results and what is expected from the complexity analysis. Finally, we discuss of the next investigations which are needed on this topic.
Type de document :
Communication dans un congrès
Proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2018, Volos, Greece. 〈http://ictai2018.org/〉
Liste complète des métadonnées

https://hal-amu.archives-ouvertes.fr/hal-01933665
Contributeur : Cyril Terrioux <>
Soumis le : vendredi 23 novembre 2018 - 21:13:08
Dernière modification le : mardi 27 novembre 2018 - 01:22:45

Fichier

ictai2018_final_V2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01933665, version 1

Collections

Citation

Philippe Jégou, Hélène Kanso, Cyril Terrioux. On the Relevance of Optimal Tree Decompositions for Constraint Networks. Proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2018, Volos, Greece. 〈http://ictai2018.org/〉. 〈hal-01933665〉

Partager

Métriques

Consultations de la notice

42

Téléchargements de fichiers

34