An Algebraic Approach Towards the Fine-Grained Complexity of Graph Coloring Problems

Ambroise Baril (1) , Miguel Couceiro (1) , Victor Lagerkvist (2)

1 ORPAILLEUR - Knowledge representation, reasonning
2 Department of Computer and Information Science - Linköping University

In this paper we are interested in the finegrained complexity of determining whether there is an homomorphism from an input graph G to a fixed graph H (the H-coloring problem). The starting point is the observation that these problems can be formulated in the language of CSPs, and that (partial) polymorphisms of binary relations are of paramount importance in the study of complexity classes of such CSPs. Thus, we first investigate the expressivity of binary symmetric relations EH and their corresponding (partial) polymorphisms pPol(EH). For irreflexive graphs we observe that there is no pair of graphs H and H such that pPol(EH) ⊆ pPol(E H), unless E H = ∅ or H =H. More generally we show the existence of an nary relation R whose partial polymorphisms strictly subsume those of H and such that CSP(R) is N Pcomplete if and only if H contains an odd cycle of length at most n. Motivated by this we also describe the sets of total polymorphisms of every nontrivial clique, every odd cycle, as well as certain cores. We finish the paper with some noteworthy questions for future research.

Domaines: Informatique [cs]; Combinatoire [math.CO]

Ambroise Baril, Miguel Couceiro, Victor Lagerkvist. An Algebraic Approach Towards the Fine-Grained Complexity of Graph Coloring Problems. 2022. ⟨hal-03424133v4⟩