On balanced CSPs with high treewidth

Thumbnail
Visualitza/Obre
Data de publicació
2007
Autor/a
Ansótegui Gil, Carlos José
Béjar Torres, Ramón
Fernàndez Camon, César
Mateu Piñol, Carles
Citació recomanada
Ansótegui Gil, Carlos José; Béjar Torres, Ramón; Fernàndez Camon, César; Mateu Piñol, Carles; . (2007) . On balanced CSPs with high treewidth. Proceedings of the twenty-second National Conference on Artificial Intelligence, 2007, p. 161-166. http://hdl.handle.net/10459.1/46640.
Impacte

Logo de Google Acadèmic  Google Acadèmic
Compartir
Exportar a Mendeley
Metadades
Mostra el registre d'unitat complet
Resum
Tractable cases of the binary CSP are mainly divided in two classes: constraint language restrictions and constraint graph restrictions. To better understand and identify the hardest binary CSPs, in this work we propose methods to increase their hardness by increasing the balance of both the constraint language and the constraint graph. The balance of a constraint is increased by maximizing the number of domain elements with the same number of occurrences. The balance of the graph is defined using the classical definition from graph the- ory. In this sense we present two graph models; a first graph model that increases the balance of a graph maximizing the number of vertices with the same degree, and a second one that additionally increases the girth of the graph, because a high girth implies a high treewidth, an important parameter for binary CSPs hardness. Our results show that our more balanced graph models and constraints result in harder instances when compared to typical random binary CSP instances, by several orders of magnitude. Also we detect, at least for sparse constraint graphs, a higher treewidth for our graph models.
URI
http://hdl.handle.net/10459.1/46640
És part de
Proceedings of the twenty-second National Conference on Artificial Intelligence, 2007, p. 161-166
Col·leccions