Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy

The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative problems (also known as list homomorphism problems) by A. Bulatov (2003). Egri et al. (SODA 2014) augmented this result by showing that for digraph templates H, every conservative CSP, denoted LHOM(H), is solvable in log space or is hard for NL. A conjecture of Larose and Tesson from 2007 forecasts that when LHOM(H) is in log space, then in fact, it falls in a small subclass of log space, the set of problems expressible in symmetric Data log. The present work verifies the conjecture for LHOM(H) (and, indeed, for the wider class of conservative CSPs with binary constraints), and by so doing sharpens the aforementioned dichotomy. A combinatorial characterization of symmetric Data log provides the language in which the algorithmic ideas of the paper, quite different from the ones in Egri et al., are formalized.