Some algorithmic results for finding compatible spanning circuits in edge-colored graphs

Zhiwei Guo, Hajo Broersma*, Ruonan Li, Shenggui Zhang

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Downloads (Pure)

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 languageEnglish
Pages (from-to)1008-1019
Number of pages12
JournalJournal of combinatorial optimization
Volume40
Issue number4
DOIs
Publication statusPublished - 1 Nov 2020

Keywords

  • UT-Hybrid-D
  • Edge-colored graph
  • NP-complete problem
  • Polynomial-time algorithm
  • Compatible spanning circuit

Fingerprint Dive into the research topics of 'Some algorithmic results for finding compatible spanning circuits in edge-colored graphs'. Together they form a unique fingerprint.

Cite this