Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 1008-1019 |
| Number of pages | 12 |
| Journal | Journal of combinatorial optimization |
| Volume | 40 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 1 Nov 2020 |
Keywords
- UT-Hybrid-D
- Edge-colored graph
- NP-complete problem
- Polynomial-time algorithm
- Compatible spanning circuit