## Hypertree Width

Given: A hypergraph.

Task: Output a hypertree decomposition.

#### What is a hypertree decompositon?

A *hypergraph* is a pair $H=(V(H),E(H))$, consisting of a set
$V(H)$ of *vertices* and a set $E(H)$ of *hyperedges*, each
hyperedge being a subset of $V(H)$.

A *tree decomposition* of a hypergraph $H=(V,E)$ is a pair
$\mathcal{T}=(T,\chi)$ where $T=(V(T),E(T))$ is a tree and $\chi$ is a mapping
that assigns each $t\in V(T)$ a set $\chi(t)\subseteq V$ (called
the *bag* at $t$) such that
the following properties hold:

1) for each $v\in V$ there is some $t\in V(T)$ with $v\in \chi(t)$
(*$v$ is covered by $t$*),

2) for each $e\in E$ there is some $t\in V(T)$ with $e \subseteq
\chi(t)$ (*$e$ is covered by $t$*),

3) for any three $t_1,t_2, t’ \in V(T)$ where $t’$ lies on the path
between $t_1$ and $t_2$, we have
$\chi(t’)\subseteq \chi(t_1)\cap \chi(t_2)$ (*bags containing the
same vertex are connected*).

Consider a hypergraph $H=(V,E)$ and a set $S\subseteq V$. An
*edge cover* of $S$ is a set $F\subseteq E$ such that for every
$v\in S$ there is some $e\in F$ with $v\in e$.

A *generalized hypertree decomposition* of $H$ is a triple
$\mathcal{G}=(T,\chi,\lambda)$ where $(T,\chi)$ is a tree decomposition of
$H$ and $\lambda$ is a mapping that assigns each $t\in V(T)$ an
*edge cover* $\lambda(t)$ of $\chi(t)$. The *width* of
$\mathcal{G}$ is the size of a largest edge cover $\lambda(t)$ over all
$t\in V(T)$. A **hypertree decomposition** is a generalized
hypertree decomposition that satisfies the following additional property:
for every $n \in V(T)$ and every $h \in \lambda(n)$, we have $h \cap \chi^+(n) \subseteq \chi(n)$,
where $T_n$ denotes the subtree of $T$ rooted at $n$, and $\chi^+(n)$ refers to the set of all vertices
occurring in $\chi$ of the subtree $T_n$ (*special condition or Decendant Condition*).

The *hypertree width* $htw(H)$ is the smallest width over all hypertree
decompositions of $H$.

We refer to [GottlobGrecoScarcello02].

### Input format

See Details

### Tracks

2a. Exact Track

2b. Heuristic Track

### Literature

[FischEtAl18]:

Wolfgang Fischl, Georg Gottlob, Reinhard Pichler. General and Fractional Hypertree Decompositions: Hard and Easy Cases. CoRR 1611.01090.

[GottlobGrecoScarcello02]: Georg Gottlob, Nicola Leone, Francesco Scarcello. Hypertree Decompositions and Tractable Queries. Journal of Computer and System Sciences. Elsevier. 2002.

[GottlobGrecoScarcello09]: Georg Gottlob, Gianluigi Greco, and Francesco Scarcello. Treewidth and Hypertree Width. ICALP’09.