10
$\begingroup$

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?
$\endgroup$
8
$\begingroup$

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.

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.

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.)

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Daniel Apon Oct 7 '10 at 19:40
  • 2
    $\begingroup$ @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. $\endgroup$ – András Salamon Oct 7 '10 at 19:57
  • $\begingroup$ @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. $\endgroup$ – András Salamon Oct 7 '10 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.