3
$\begingroup$

Generalized hypertree width is a tree-width-like parameter for hypergraphs, which plays an important role in the study of constraint satisfaction problems and related areas. For its more well-known cousin, namely tree-width, there is a well-established theory detailing the "obstructions" for having small tree-width; for example, it is known that if a graph has tree-width at least $k$ then it contains as a minor the $f(k) \times f(k)$ grid, for $f(k)$ which grows with $k$ (this is the Excluded Grid Theorem).

My question is as follows: is there a similar theory for generalized hypertree width? In the paper Adler, I.; Gottlob, G.; Grohe, M. (2007). Hypertree width and related hypergraph invariants. European Journal of Combinatorics, Vol. 28(8), 2167-2181 I found some generalizations to the setting of hypertree decompositions of notions from graph minor theory (such as brambles and tangles), but nothing as developed as the Excluded Grid Theorem. What is the current state of research/knowledge on this issue?

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .