Apple Keyboards: curse of the paragraph key

I’ve been doing a fair bit of typing on a new Apple wired keyboard.

STACS 2009

STACS 2009 was held 26 to 28 February 2009 in Freiburg, Germany.  Several papers are relevant to constraints, here are rather biased synopses of two of these.

Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, and Dániel Marx: Enumerating Homomorphisms

Let ECSP(S,T) be the problem instance that requires generating all homomorphisms from S to T.  For classes A and B of relational structures, all with the same finite signature, let ECSP(A,B) be the problem consisting of all instances ECSP(S,T) where S is in A and T is in B.  (In particular, the fixed finite signature means that only constraint satisfaction problems of bounded arity are dealt with here.)  In general ECSP has exponentially many solutions, so of interest are A and B that lead to a procedure to generate all solutions in time that is polynomial in the total size of the input and the output.  The main focus of this paper are conditions that guarantee that solutions can be computed with polynomial delay (WPD), which guarantees polynomial total time.

Lemma 3.3 is interesting: for a fixed core T, and letting be the class of disjoint unions of structures S and T where there is a homomorphism from S to T, the decision problem CSP(_,T) is in PTIME iff the problem of finding a solution SCSP(,_) is in PTIME.  Lemma 3.4 similarly relates SCSP and ECSP: for a class A of relational structures, let A’ be the class of structures constructed from A by adding |A| new independent vertices to each structure; then SCSP(A,_) is in PTIME iff ECSP(A’,_) is in PTIME.  Theorem 4.10 states that if A is a class of structures such that the k-core of each structure in A has tree width at most k, then ECSP(A,_) is solvable WPD.  Let CQE(A,B) be the problem of enumerating all extendible partial mappings from a given subset of the vertices of the given source structure S from A to the given target structure T from B, in the sense that the partial mapping can be extended to a homomorphism from S to T.  For a particular class A whose 2-cores have bounded width, Example 6.2 shows that if CQE(A,_) is solvable WPD, then W[1] = FPT.

Dániel Marx: Tractable Structures for Constraint Satisfaction with Truth Tables

This paper deals with unbounded arity problems which are represented as truth tables.  Most of the work on complexity of constraint satisfaction has focused on listing all tuples in each relational structure in the instance.  A truth table representation is a generalized adjacency matrix: instead of listing a tuple, a 1 represents its presence.  For sparse problems truth tables are therefore very large, but for dense problems they are reasonable.  The main result is Theorem 1.5: assuming a conjecture of the author, CSP(A,_) is tractable iff the class of hypergraphs of structures in A has bounded adaptive width.  Adaptive width is a new measure based on fractional independent sets that (Proposition 5.1) is at most as large as fractional hypertree width.  Previously fractional hypertree width was the most general width measure known that guaranteed tractability.