THE COMPLEXITY OF MATROID HOMOMORPHISM RECONFIGURATION

作     者：Heo, Cheolwon Siggers, Mark 

作者机构：Applied Algebra and Optimization Research Center Sungkyunkwan University 2066 Seobu-ro Gyeonggi-do Suwon-si16419 Korea Republic of Kyungpook National University Mathematics Department 80 Dae-hak-ro Buk-gu Daegu41566 Korea Republic of 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2025年

核心收录：

摘      要：We consider a reconfiguration version of the homomorphism problem HomM(N) for binary matroids N. This reconfiguration problem, RecolM(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 is, or dismantles to, the graphic matroid M(K2), and that the problem is PSPACE-complete when N is the graphic matroid M(K3), M(K4), or any graphic matroid containing M(K5).MSC Codes 05C15, 05B35 © 2025, CC BY.