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.



Titolo: Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
Autori: 
GRECO, Gianluigi
SCARCELLO, Francesco
Data di pubblicazione: 2017
Rivista: 
INFORMATION AND COMPUTATION  
Citazione: Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems / Greco, Gianluigi; Scarcello, Francesco. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 252(2017), pp. 201-220.
Handle: http://hdl.handle.net/20.500.11770/133791
Appare nelle tipologie:1.1 Articolo in rivista

File in questo prodotto:
Non ci sono file associati a questo prodotto.
Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/20.500.11770/133791
  • Citazioni
  • ND

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
 
 
 
Powered by IRIS-about IRIS-Utilizzo dei cookie
Logo CINECA  Copyright © 2020