English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Tree projections provide a mathematical framework that encompasses all thevarious (purely) structural decomposition methods that have been proposed inthe literature to single out classes of nearly-acyclic (hyper)graphs, such asthe tree decomposition method, which is the most powerful decomposition methodon graphs, and the (generalized) hypertree decomposition method, which is itsnatural counterpart on arbitrary hypergraphs. The paper analyzes thisframework, by focusing in particular on "minimal" tree projections, that is, ontree projections without useless redundancies. First, it is shown that minimaltree projections enjoy a number of properties that are usually required fornormal form decompositions in various structural decomposition methods. Inparticular, they enjoy the same kind of connection properties as (minimal) treedecompositions of graphs, with the result being tight in the light of thenegative answer that is provided to the open question about whether they enjoya slightly stronger notion of connection property, defined to speed-up thecomputation of hypertree decompositions. Second, it is shown that treeprojections admit a natural game-theoretic characterization in terms of theCaptain and Robber game. In this game, as for the Robber and Cops gamecharacterizing tree decompositions, the existence of winning strategies impliesthe existence of monotone ones. As a special case, the Captain and Robber gamecan be used to characterize the generalized hypertree decomposition method,where such a game-theoretic characterization was missing and asked for. Besidestheir theoretical interest, these results have immediate algorithmicapplications both for the general setting and for structural decompositionmethods that can be recast in terms of tree projections.

Tree Projections and Structural Decomposition Methods: Minimality and Game-Theoretic Characterization