TITLE: Hardness of 4-coloring G-colorable graphs.
ABSTRACT:
Constraint satisfaction problems (CSPs) are widely studied as their framework is very general and includes a wide variety of computational problems. Any CSP can be cast as a decision problem CSP(H): is there a homomorphism from the input structure I to some fixed structure H? For example, CSP(K_m) is the problem of deciding whether there exists a map from the input graph I to the m-clique K_m, i.e, m-colorability of I.
A natural approximation version of CSP(H), denoted PCSP(G,H), asks to distinguish between structures which can be mapped to G and which cannot be mapped even to H. For instance, PCSP(K_10, K_20) asks to distinguish 10-colorable and not even 20-colorable graphs.
While all CSPs (over finite domain) are known to be either in P or NP-complete, there is no such dichotomy for PCSPs.
In this talk I will:
1. Present a general algebraic approach (of Barto, Bulín, Krokhin, Opršal) to proving NP-hardness of PCSP(G,H), where G, H are arbitrary structures.
2. Show how this approach can be used to prove that both PCSP(G,K_3) and PCSP(G,K_4) are NP-hard for any (non-bipartite) graph G (and why it does not work already for PCSP(G,K_5)). This part involves Lovász-style translation from the graph language to a quantitative topology problem and is a joint work with Filakovský, Opršal, Tasinato, and Wagner.