Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems

Dantchev, Stefan; Madelaine, Florent

Abstract

Forbidden Pattern problem (FPP) is a proper generalisation of Constraint Satisfaction Problem (CSP). FPP is related to MMSNP, a logic introduced in relation with CSP by Feder and Vardi. We prove that Forbidden Pattern Problems are Constraint Satisfaction Problems when restricted to graphs of bounded degree. This result is 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) involving both vertex- and edge-colorings of the graph F, and thus allowing to express NP-complete problems (while F-moteness is always in P). We finally extend our result to arbitrary structures (not only graphs) and prove that every problem in MMSNP, restricted to connected input of bounded degree, is in fact in CSP.

Citation

Dantchev, S., & Madelaine, F. (2006). Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems. In D. Grigoriev, J. Harrison, & E. A. Hirsch (Eds.), . https://doi.org/10.1007/11753728_18

• Conference Name: International Computer Science Symposium in Russia.
• Conference Location: St. Peterburg, Russia
• Publication Date: 2006
• Publisher: Springer Verlag
• Volume: 3967
• Pages: 159-170
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• ISBN: 978-3-540-34166-6
• DOI: https://doi.org/10.1007/11753728_18
• Public URL: https://durham-repository.worktribe.com/output/1162805
• Publisher URL: /f.r.madelaine/Download/BoundedDegreeWithAppendix.ps.gz