CSPs with unbounded fractional hypertree width

Question

At SODA 2006, Martin Grohe and D$\acute{\rm a}$niel Marx's paper "Constraint solving via fractional edge covers" (ACM citation) showed that for the class of hypergraphs $H$ with bounded fractional hypertree width, CSP($H$) $\in PTIME$.

Definitions, etc.

For a great survey of standard tree decompositions and treewidth, see here (Thanks ahead of time, JeffE!).

Let $H$ be a hypergraph.

Then for a hypergraph $H$ and a mapping $\gamma : E(H) \rightarrow [0,\infty)$,

$B(\gamma) = ${$v \in V(H) : \sum_{e \in V(H), v \in e} \gamma(e) \ge 1$}.

Additionally, let weight($\gamma$) = $\sum_{e \in E}\gamma(e)$.

Then a fractional hypertree decomposition of $H$ is a triple $(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$, where:

• $(T, (B_t)_{t \in V(T)})$ is a tree decomposition of $H$, and
• $(\gamma_t)_{t \in V(T)}$ is a family of mappings from $E(H)$ to $[0, \infty)$ s.t. for every $t \in V(T), B_t \subseteq B(\gamma_t)$.

Then we say the width of $(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$ is $\max${weight$(\gamma_t), t \in V(T)$}.

Finally, the fractional hypertree width of $H$, fhw($H$), is the minimum of the widths over all possible fractional hypertree decompositions of $H$.

Question

As stated above, if the fractional hypertree width of the underlying graph of a CSP is bounded by a constant, then there is a polynomial time algorithm to solve the CSP. However, it was left as an open problem at the end of the linked paper whether there were any polynomial-time solvable families of CSP instances having unbounded hypertree width. (I should also point out, this question is completely resolved in the case of bounded vs. unbounded treewidth (ACM citation) under the assumption that $FPT \ne W[1]$.) Since there's been some time since the first-linked paper, plus I'm relatively unaware of the general state of this sub-field, my question is:

Is anything known about the (in)tractability of CSPs over graphs with unbounded fractional hypertree width?

Answer 1

You linked to two papers, both with conjectures. I presume you mean Grohe's 2007 conjecture.

This question was answered in 2008:

Theorem 5. CSP(C$_0$,_) is in NP, but neither in P nor NP-complete (unless P = NP). Moreover, the set C$_0$ can be decided in deterministic polynomial time.

• Manuel Bodirsky and Martin Grohe, Non-dichotomies in Constraint Satisfaction Complexity, ICALP 2008. doi:10.1007/978-3-540-70583-3_16 (PDF)

The idea is to blow holes in the instance sizes of CLIQUE, by the same delayed diagonalization technique introduced by Ladner for his theorem. Note that the set C$_0$ contains arbitrarily large cliques, and the fractional hypertree width of an $n$-clique is $n/2$. So it is possible to have CSPs of the form CSP(A,_) that are of intermediate complexity, where A has unbounded fractional hypertree width. This answers Grohe's conjecture in the negative.

At the same conference Chen, Thurley, and Weyer had a paper with a similar result, but that required strong embeddings so technically wasn't of the right form for the conjecture.

• Yijia Chen, Marc Thurley, and Mark Weyer, Understanding the Complexity of Induced Subgraph Isomorphisms, ICALP 2008. doi:10.1007/978-3-540-70575-8_48 (PDF)

Finally, any class of CSP instances can be transformed into a representation with worst-case fractional hypertree width. In many cases this transformation is polynomially bounded in size and can be done in polynomial time. This means that it is easy to generate CSPs with unbounded fractional hypertree width, even modulo homomorphic equivalence. These CSPs are not going to be of the form CSP(A,_) since the target structures are special, but they do provide a neat reason why the CSPs defined by restricting just the source structures are not all that interesting: it is often just too easy to hide the tree-like structure of a CSP instance by changing the representation so that the source structure has large width. (This is discussed in chapter 7 of my thesis.)