Talk information

Date: Sunday, December 14, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Sergey Avvakumov (Tel Aviv University)
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 map (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.