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.