Revisiting Graph Width Measures for CNFEncodings We consider bounded width CNFformulas where the width is measured by popular graph width measures on graphs associated to CNFformulas. Such restricted graph classes, in particular those of bounded treewidth, have been extensively studied for their uses in the design of algorithms for various computational problems on CNFformulas. Here we consider the expressivity of these formulas in the model of clausal encodings with auxiliary variables. We first show that bounding the width for many of the measures from the literature leads to a dramatic loss of expressivity, restricting the formulas to such of low communication complexity. We then show that the width of optimal encodings with respect to different measures is strongly linked: there are two classes of width measures, one containing primal treewidth and the other incidence cliquewidth, such that in each class the width of optimal encodings only differs by constant factors. Moreover, between the two classes the width differs at most by a factor logarithmic in the number of variables. Both these results are in stark contrast to the setting without auxiliary variables where all width measures we consider here differ by more than constant factors and in many cases even by linear factors.

Relational Width of FirstOrder Expansions of Homogeneous Graphs with Bounded Strict Width. Solving the algebraic dichotomy conjecture for constraint satisfaction problems over structures firstorder definable in countably infinite finitely bounded homogeneous structures requires understanding the applicability of localconsistency methods in this setting. We study the amount of consistency (measured by relational width) needed to solve CSP for firstorder expansions S of countably infinite homogeneous graphs that additionally have bounded strict width, i.e., for which establishing local consistency of an instance of the CSP not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking.  :101,main result is that the structures S under consideration have relational width exactly (2, L) where L is the maximal size of a forbidden subgraph of a homogeneous graph under consideration, but not smaller than 3. It beats the upper bound (2m, 3m) where m  max(arity(S)1, L, 3) and arity(S) is the largest arity of a relation in S, which follows from a sufficient condition implying bounded relational width from the literature. Since L may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures , whose relational width, if finite, is always at most (2,3).