Kaydedildi:
| Yazar: | |
|---|---|
| Materyal Türü: | Recurso digital |
| Dil: | |
| Baskı/Yayın Bilgisi: |
Zenodo
2025
|
| Konular: | |
| Online Erişim: | https://doi.org/10.5281/zenodo.17445804 |
| Etiketler: |
Etiketle
Etiket eklenmemiş, İlk siz ekleyin!
|
| _version_ | 1866901260404260864 |
|---|---|
| author | SÉRGIO DE ANDRADE, PAULO |
| author_facet | SÉRGIO DE ANDRADE, PAULO |
| contents | This paper investigates the complexity landscape of graph homomorphism problems, with a specific focus on how restricting the classes of input or target graphs leads to sharp dichotomies between tractable (polynomial-time solvable) and intractable (NP-complete) problems. We survey seminal results, including the Hell-Nešetřil theorem for undirected target graphs, and its generalization to directed graphs, which was resolved through the proof of the Feder-Vardi conjecture. The analysis extends to variations such as list homomorphisms and locally constrained homomorphisms, where similar dichotomous behavior is observed. Furthermore, the impact of structural parameters on the input graph class, such as bounded treewidth or planarity, is examined. By synthesizing these results, the paper highlights the recurring theme of dichotomy in constraint satisfaction problems and outlines the key structural and algebraic properties, such as bipartiteness, cores, and the presence of certain polymorphisms, that delineate the boundary of computational tractability. |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_17445804 |
| institution | Zenodo |
| language | |
| publishDate | 2025 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Complexity Dichotomies for Graph Homomorphism Problems on Restricted Classes SÉRGIO DE ANDRADE, PAULO Graph Homomorphism Complexity Dichotomy Constraint Satisfaction Problems Hell-Nešetřil Theorem Feder-Vardi Conjecture Bounded Treewidth List Homomorphism This paper investigates the complexity landscape of graph homomorphism problems, with a specific focus on how restricting the classes of input or target graphs leads to sharp dichotomies between tractable (polynomial-time solvable) and intractable (NP-complete) problems. We survey seminal results, including the Hell-Nešetřil theorem for undirected target graphs, and its generalization to directed graphs, which was resolved through the proof of the Feder-Vardi conjecture. The analysis extends to variations such as list homomorphisms and locally constrained homomorphisms, where similar dichotomous behavior is observed. Furthermore, the impact of structural parameters on the input graph class, such as bounded treewidth or planarity, is examined. By synthesizing these results, the paper highlights the recurring theme of dichotomy in constraint satisfaction problems and outlines the key structural and algebraic properties, such as bipartiteness, cores, and the presence of certain polymorphisms, that delineate the boundary of computational tractability. |
| title | Complexity Dichotomies for Graph Homomorphism Problems on Restricted Classes |
| topic | Graph Homomorphism Complexity Dichotomy Constraint Satisfaction Problems Hell-Nešetřil Theorem Feder-Vardi Conjecture Bounded Treewidth List Homomorphism |
| url | https://doi.org/10.5281/zenodo.17445804 |