TY - JOUR
T1 - Some algorithmic results for finding compatible spanning circuits in edge-colored graphs
AU - Guo, Zhiwei
AU - Broersma, Hajo
AU - Li, Ruonan
AU - Zhang, Shenggui
N1 - Springer deal
PY - 2020/11/1
Y1 - 2020/11/1
N2 - A compatible spanning circuit in a (not necessarily properly) edge-colored graph G is a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. Sufficient conditions for the existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and Euler tours), and polynomial-time algorithms for finding compatible Euler tours have been considered in previous literature. More recently, sufficient conditions for the existence of more general compatible spanning circuits in specific edge-colored graphs have been established. In this paper, we consider the existence of (more general) compatible spanning circuits from an algorithmic perspective. We first show that determining whether an edge-colored connected graph contains a compatible spanning circuit is an NP-complete problem. Next, we describe two polynomial-time algorithms for finding compatible spanning circuits in edge-colored complete graphs. These results in some sense give partial support to a conjecture on the existence of compatible Hamilton cycles in edge-colored complete graphs due to Bollobás and Erdős from the 1970s.
AB - A compatible spanning circuit in a (not necessarily properly) edge-colored graph G is a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. Sufficient conditions for the existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and Euler tours), and polynomial-time algorithms for finding compatible Euler tours have been considered in previous literature. More recently, sufficient conditions for the existence of more general compatible spanning circuits in specific edge-colored graphs have been established. In this paper, we consider the existence of (more general) compatible spanning circuits from an algorithmic perspective. We first show that determining whether an edge-colored connected graph contains a compatible spanning circuit is an NP-complete problem. Next, we describe two polynomial-time algorithms for finding compatible spanning circuits in edge-colored complete graphs. These results in some sense give partial support to a conjecture on the existence of compatible Hamilton cycles in edge-colored complete graphs due to Bollobás and Erdős from the 1970s.
KW - UT-Hybrid-D
KW - Edge-colored graph
KW - NP-complete problem
KW - Polynomial-time algorithm
KW - Compatible spanning circuit
UR - http://www.scopus.com/inward/record.url?scp=85090309395&partnerID=8YFLogxK
U2 - 10.1007/s10878-020-00644-7
DO - 10.1007/s10878-020-00644-7
M3 - Article
AN - SCOPUS:85090309395
VL - 40
SP - 1008
EP - 1019
JO - Journal of combinatorial optimization
JF - Journal of combinatorial optimization
SN - 1382-6905
IS - 4
ER -