What's the correlation between treewidth and instance hardness for random 3-SAT? This recent paper from FOCS2013, Strong Backdoors to Bounded Treewidth SAT by Gaspers and Szeider talks about the link between the treewidth of the SAT clause graph and instance hardness.


  For random 3-SAT, i.e. 3-SAT instances chosen at random, what is the correlation between treewidth of the clause graph and instance hardness?


"Instance hardness" can be taken as "hard for a typical SAT solver", i.e. running time.

I am looking for either theoretical or empirical style answers or references. To my knowledge, there do not seem to be empirical studies on this. I am aware there are somewhat different ways to build SAT clause graphs, but this question is not focused on the distinction.

Maybe a natural closely related question is how treewidth of the clause graph relates to the 3-SAT phase transition.
Not really an answer but the closest references I am aware of. There are results available for branch-width. Also, there is at least one empirical study of treewidth of industrial instances.


Discovering treewidth, H. Bodlaender, 2005. Gives algorithms to compute bounds on treewidth.
Treewidth in Industrial SAT Benchmarks, R. Mateescu, 2011. Uses variations of above algorithms to estimate treewidth of SAT2009 competition benchmarks.
Algorithms and complexity results for #SAT and Bayesian inference, F. Bacchus S. Dalmao, T. Pitassi, 2003. Relates branch-width to complexity of #SAT, 2003.
Satisfiability, branch-width and tseitin tautologies, Alekhnovich, Razborov, 2002.