Bounded-Degree Forbidden Patterns Problems Are Constraint Satisfaction Problems

Forbidden Patterns problem (FPP) is a proper generalisation of Constraint Satisfaction Problem (CSP). FPP was introduced in [1] as a combinatorial counterpart of MMSNP, a logic which was in turn introduced in relation to CSP by Feder and Vardi [2]. We prove that

Forbidden Patterns Problems are Constraint Satisfaction Problems

when restricted to

graphs of bounded degree

. This is a generalisation of a result by Häggkvist and Hell who showed that

F

-moteness of bounded-degree graphs is a CSP (that is, for a given graph

F

there exists a graph

H

so that the class of bounded-degree graphs that do not admit a homomorphism from

F

is exactly the same as the class of bounded-degree graphs that are homomorphic to

H

). Forbidden-pattern property is a strict generalisation of

F

-moteness (in fact of

F

-moteness combined with a CSP) as it involves both vertex- and edge-colourings of the graph

F

, and thus allows to express

$\mathcal{N}p$

-complete problems (while

F

-moteness is always in

$\mathcal{P}$

). We finally extend our result to arbitrary relational structures, and prove that every problem in MMSNP, restricted to connected inputs of bounded (hyper-graph) degree, is in fact in CSP.