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

详细信息    查看全文

• 关键词：Structural decomposition methods ; Games on discrete structures ; Conjunctive queries and databases ; Constraint satisfaction problems ; Hypertree decompositions ; Tree projections ; Homomorphism problem
• 刊名：Information and Computation
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：252
• 期：Complete
• 页码：201-220
• 全文大小：1127 K
• 卷排序：252

文摘

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.