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

<p>This question was answered in 2008:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<ul>
<li>Manuel Bodirsky and Martin Grohe, <em>Non-dichotomies in Constraint Satisfaction Complexity</em>, ICALP 2008.  <a href="https://dx.doi.org/10.1007/978-3-540-70583-3_16" rel="nofollow noreferrer">doi:10.1007/978-3-540-70583-3_16</a> (<a href="http://www.lix.polytechnique.fr/~bodirsky/publications/nodich.pdf" rel="nofollow noreferrer">PDF</a>)</li>
</ul>

<p>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.</p>

<p>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.</p>

<ul>
<li>Yijia Chen, Marc Thurley, and Mark Weyer, <em>Understanding the Complexity of Induced Subgraph Isomorphisms</em>, ICALP 2008.  <a href="https://dx.doi.org/10.1007/978-3-540-70575-8_48" rel="nofollow noreferrer">doi:10.1007/978-3-540-70575-8_48</a> (<a href="http://basics.sjtu.edu.cn/~chen/papers/icalp.pdf" rel="nofollow noreferrer">PDF</a>)</li>
</ul>

<p>Finally, <em>any</em> 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 <a href="https://ora.ox.ac.uk/objects/uuid:5d641fff-4d95-43b2-9ff8-73395d782ad8" rel="nofollow noreferrer">thesis</a>.)</p>

CC BY-SA 4.0
2022-03-25T20:40:55.510Z
@AndrásSalamon Does any width parametes beyond treewidth (hypertree width and beyond; e.g., "Tractable Hypergraph Properties for Constraint Satisfaction
and Conjunctive Queries" Fig 2) base on the assumption that arity of the constraint can be unbounded? This assumption works fine in CSP but for conjunctive queries, it doesn't seem right because it means a relation can have unbounded arity. Do I misunderstand anything?
xxks-kkk
CC BY-SA 2.5
2010-10-07T19:40:15.850Z
thanks for the great response.

A quick follow-up question: My reading of "The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side" is that there does exist a P vs. NP-c dichotomy for CSPs of the form CSP(C,_) for non-hypergraphs of bounded arity, am I correct in believing so? Or more to the point -- there's no hidden assumption/conjecture in Corollary 6.1 of this paper that I'm unaware of, is there? Or further, is the dichotomy there simply P vs. not-P? (Sorry if this is obvious.)
Daniel Apon
CC BY-SA 2.5
2010-10-07T19:57:41.020Z
@Daniel: This paper was not so much about dichotomies but about precisely characterizing the tractable structure-restricted cases as those of bounded width.  Bounded width was known to imply tractable, but the key part of Grohe's paper is in the other direction.  Unbounded width implies embedding grid minors of arbitrarily large size, which one can then use to encode an NP-hard problem like CLIQUE.  The Feder/Vardi dichotomy conjecture for CSPs is for CSP(\_,B) type restrictions, which are believed to be either in P or NP-complete.
András Salamon
CC BY-SA 2.5
2010-10-07T21:15:39.817Z
@Daniel: By the way, this stuff certainly wasn't obvious to me the first time I read it.  The snappy summary of Grohe's paper in my previous comment owes a lot to Dave Cohen.
András Salamon
CC BY-SA 3.0
2010-10-07T19:14:50.687Z
2017-03-26T17:40:32.927Z
2017-03-26T17:40:32.927Z
András Salamon
<p>At SODA 2006, Martin Grohe and D$\acute{\rm a}$niel Marx's paper "Constraint solving via fractional edge covers" (<a href="http://portal.acm.org/citation.cfm?id=1109590">ACM citation</a>) showed that for the class of hypergraphs $H$ with bounded fractional hypertree width, CSP($H$) $\in PTIME$.</p>

<p><strong>Definitions, etc.</strong></p>

<p>For a great survey of standard tree decompositions and treewidth, see <a href="http://compgeom.cs.uiuc.edu/~jeffe/teaching/comptop/notes/treewidth.pdf">here</a> (Thanks ahead of time, JeffE!).</p>

<p>Let $H$ be a hypergraph.</p>

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

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

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

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

<ul>
<li> $(T, (B_t)_{t \in V(T)})$ is a tree decomposition of $H$, and
<li> $(\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)$.
</ul>

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

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

<p><strong>Question</strong></p>

<p>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 (<a href="http://portal.acm.org/citation.cfm?id=1206036">ACM citation</a>) 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:</p>

<blockquote>
Is <i>anything</i> known about the (in)tractability of CSPs over graphs with unbounded fractional hypertree width?
</blockquote>

<cc.complexity-theory><graph-theory><hypergraphs><treewidth><csp>
CSPs with unbounded fractional hypertree width
Daniel Apon
# CSPs with unbounded fractional hypertree width

(Asked by: username_0 on 2010-10-07)

At SODA 2006, Martin Grohe and D$\acute{\rm a}$niel Marx's paper "Constraint solving via fractional edge covers" ([ACM citation](http://portal.acm.org/citation.cfm?id=1109590)) 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](http://compgeom.cs.uiuc.edu/~jeffe/teaching/comptop/notes/treewidth.pdf) (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](http://portal.acm.org/citation.cfm?id=1206036)) 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?

**Tags:** cc.complexity-theory, graph-theory, hypergraphs, treewidth, csp

---

## 1 answers

### Answer by username_1 on 2010-10-07. Score: 8 | Accepted answer

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](https://dx.doi.org/10.1007/978-3-540-70583-3_16) ([PDF](http://www.lix.polytechnique.fr/~bodirsky/publications/nodich.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](https://dx.doi.org/10.1007/978-3-540-70575-8_48) ([PDF](http://basics.sjtu.edu.cn/~chen/papers/icalp.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](https://ora.ox.ac.uk/objects/uuid:5d641fff-4d95-43b2-9ff8-73395d782ad8).)

> **Comments:**
> **username_0**: thanks for the great response.  A quick follow-up question: My reading of "The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side" is that there does exist a P vs. NP-c dichotomy for CSPs of the form CSP(C,_) for non-hypergraphs of bounded arity, am I correct in believing so? Or more to the point -- there's no hidden assumption/conjecture in Corollary 6.1 of this paper that I'm unaware of, is there? Or further, is the dichotomy there simply P vs. not-P? (Sorry if this is obvious.)  
> **username_1**: @Daniel: This paper was not so much about dichotomies but about precisely characterizing the tractable structure-restricted cases as those of bounded width.  Bounded width was known to imply tractable, but the key part of Grohe's paper is in the other direction.  Unbounded width implies embedding grid minors of arbitrarily large size, which one can then use to encode an NP-hard problem like CLIQUE.  The Feder/Vardi dichotomy conjecture for CSPs is for CSP(\_,B) type restrictions, which are believed to be either in P or NP-complete.  
> **username_1**: @Daniel: By the way, this stuff certainly wasn't obvious to me the first time I read it.  The snappy summary of Grohe's paper in my previous comment owes a lot to Dave Cohen.  
> **username_2**: @AndrásSalamon Does any width parametes beyond treewidth (hypertree width and beyond; e.g., "Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries" Fig 2) base on the assumption that arity of the constraint can be unbounded? This assumption works fine in CSP but for conjunctive queries, it doesn't seem right because it means a relation can have unbounded arity. Do I misunderstand anything?  

---

