Most structural decomposition methods can be characterized through hypergraph games that are variations of the Robber and Cops graph game that characterizes the notion of treewidth. Decomposition trees correspond to monotone winning strategies of the cops, where the escape space of the robber on the hypergraph is shrunk monotonically. Cops using non-monotonic strategies are more powerful, but such strategies do not correspond to valid decompositions, in general. The paper provides a general way to exploit the power of non-monotonic strategies, by allowing a “greedy” form of non-monotonicity. It is shown that deciding the existence of a (non-monotone) greedy winning strategy (and compute one, if any) is tractable. Moreover, from greedy strategies we can compute valid decomposition trees efficiently. As a consequence, we are able to add power to structural methods and to obtain larger islands of tractability, such as the one based on the new notion of greedy hypertree decomposition.

Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems

GRECO, Gianluigi;SCARCELLO, Francesco
2017

Abstract

Most structural decomposition methods can be characterized through hypergraph games that are variations of the Robber and Cops graph game that characterizes the notion of treewidth. Decomposition trees correspond to monotone winning strategies of the cops, where the escape space of the robber on the hypergraph is shrunk monotonically. Cops using non-monotonic strategies are more powerful, but such strategies do not correspond to valid decompositions, in general. The paper provides a general way to exploit the power of non-monotonic strategies, by allowing a “greedy” form of non-monotonicity. It is shown that deciding the existence of a (non-monotone) greedy winning strategy (and compute one, if any) is tractable. Moreover, from greedy strategies we can compute valid decomposition trees efficiently. As a consequence, we are able to add power to structural methods and to obtain larger islands of tractability, such as the one based on the new notion of greedy hypertree decomposition.
Structural decomposition methods; Games on discrete structures; Conjunctive queries and databases
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/133791
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 6
social impact