The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911840439631872 |
|---|---|
| author | Baril, Ambroise Couceiro, Miguel Lagerkvist, Victor |
| author_facet | Baril, Ambroise Couceiro, Miguel Lagerkvist, Victor |
| contents | In this paper we are interested in the fine-grained complexity of deciding whether there is a homomorphism from an input graph $G$ to a fixed graph $H$ (the $H$-Coloring problem). The starting point is that these problems can be viewed as constraint satisfaction problems (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 $E_H$ and their corresponding (partial) polymorphisms pPol($E_H$). For irreflexive graphs we observe that there is no pair of graphs $H$ and $H'$ such that pPol($E_H$) $\subseteq$ pPol($E_{H'}$), unless $E_{H'}= \emptyset$ or $H =H'$. More generally we show the existence of an $n$-ary relation $R$ whose partial polymorphisms strictly subsume those of $H$ and such that CSP($R$) is NP-complete 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 nontrivial cliques, odd cycles, as well as certain cores, and we give an algebraic characterization of projective cores. As a by-product, we settle the Okrasa and Rzążewski conjecture for all graphs of at most 7 vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_09798 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture Baril, Ambroise Couceiro, Miguel Lagerkvist, Victor Computational Complexity Combinatorics In this paper we are interested in the fine-grained complexity of deciding whether there is a homomorphism from an input graph $G$ to a fixed graph $H$ (the $H$-Coloring problem). The starting point is that these problems can be viewed as constraint satisfaction problems (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 $E_H$ and their corresponding (partial) polymorphisms pPol($E_H$). For irreflexive graphs we observe that there is no pair of graphs $H$ and $H'$ such that pPol($E_H$) $\subseteq$ pPol($E_{H'}$), unless $E_{H'}= \emptyset$ or $H =H'$. More generally we show the existence of an $n$-ary relation $R$ whose partial polymorphisms strictly subsume those of $H$ and such that CSP($R$) is NP-complete 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 nontrivial cliques, odd cycles, as well as certain cores, and we give an algebraic characterization of projective cores. As a by-product, we settle the Okrasa and Rzążewski conjecture for all graphs of at most 7 vertices. |
| title | The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2404.09798 |