Faster algorithms for graph homomorphism via tractable constraint satisfaction
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910034058805248 |
|---|---|
| author | Carbonnel, Clément |
| author_facet | Carbonnel, Clément |
| contents | We show that the existence of a homomorphism from an $n$-vertex graph $G$ to an $h$-vertex graph $H$ can be decided in time $2^{O(n)}h^{O(1)}$ and polynomial space if $H$ comes from a family of graphs that excludes a topological minor. The algorithm is based on a reduction to a single-exponential number of constraint satisfaction problems over tractable languages and can handle cost minimization. We also present an improved randomized algorithm for the special case where the graph $H$ is an odd cycle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23000 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Faster algorithms for graph homomorphism via tractable constraint satisfaction Carbonnel, Clément Computational Complexity Discrete Mathematics We show that the existence of a homomorphism from an $n$-vertex graph $G$ to an $h$-vertex graph $H$ can be decided in time $2^{O(n)}h^{O(1)}$ and polynomial space if $H$ comes from a family of graphs that excludes a topological minor. The algorithm is based on a reduction to a single-exponential number of constraint satisfaction problems over tractable languages and can handle cost minimization. We also present an improved randomized algorithm for the special case where the graph $H$ is an odd cycle. |
| title | Faster algorithms for graph homomorphism via tractable constraint satisfaction |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2602.23000 |