The complexity of matroid homomorphism reconfiguration
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915212950503424 |
|---|---|
| author | Heo, Cheolwon Siggers, Mark |
| author_facet | Heo, Cheolwon Siggers, Mark |
| contents | We consider a reconfiguration version of the homomorphism problem ${\rm Hom}_\mathbb{M}(N)$ for binary matroids $N$. This reconfiguration problem, ${\rm Recol}_\mathbb{M}(N)$, asks, for two homomorphisms $ϕ$ and $ψ$ of a matroid $M$ to $N$, if there is a path of homomorphism from $ϕ$ to $ψ$ such that consecutive homomorphism in the path differ on a single cocircuit of $N$. We show that this problem is trivial in the case that $N$ dismantles to the graphic matroid $M(K_2)$, and that the problem is ${\rm PSPACE}$-complete when $N$ is the graphic matroid $M(K_3)$, $M(K_4)$, or any graphic matroid containing $M(K_5)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_19181 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The complexity of matroid homomorphism reconfiguration Heo, Cheolwon Siggers, Mark Combinatorics 05C15, 05B35 We consider a reconfiguration version of the homomorphism problem ${\rm Hom}_\mathbb{M}(N)$ for binary matroids $N$. This reconfiguration problem, ${\rm Recol}_\mathbb{M}(N)$, asks, for two homomorphisms $ϕ$ and $ψ$ of a matroid $M$ to $N$, if there is a path of homomorphism from $ϕ$ to $ψ$ such that consecutive homomorphism in the path differ on a single cocircuit of $N$. We show that this problem is trivial in the case that $N$ dismantles to the graphic matroid $M(K_2)$, and that the problem is ${\rm PSPACE}$-complete when $N$ is the graphic matroid $M(K_3)$, $M(K_4)$, or any graphic matroid containing $M(K_5)$. |
| title | The complexity of matroid homomorphism reconfiguration |
| topic | Combinatorics 05C15, 05B35 |
| url | https://arxiv.org/abs/2503.19181 |