On the Parallel Complexity of the Alternating Hamiltonian Cycle Problem

Evripidis Bampis, Yannis Manoussakis, Ioannis MilisCombinatorics and Computer Science 1995 · DOI

TL;DR

This paper tackles the problem of finding an "alternating Hamiltonian cycle" in a 2-edge-colored complete graph. The authors introduce a novel characterization for the existence of such a cycle, which leads to a new parallel algorithm that runs in logarithmic time with polynomial processors, placing the problem in the RNC complexity class. This work also yields an improved sequential algorithm.

What Problem Does This Paper Address?

The paper investigates the "alternating Hamiltonian cycle problem" (AHC) in 2-edge-colored complete graphs. A Hamiltonian cycle is a path that visits every vertex exactly once and returns to the starting vertex. In this context, the edges of the complete graph are colored with two distinct colors (say, red and blue), and an alternating Hamiltonian cycle is one where adjacent edges in the cycle must have different colors.

While the AHC problem is known to be NP-complete for general graphs, it becomes more tractable for complete graphs. Previous work has established conditions for the existence of such cycles, often based on vertex degrees or structural properties. However, these results haven't directly translated into efficient parallel algorithms. This paper aims to bridge this gap by developing a parallel algorithm for finding an AHC in 2-edge-colored complete graphs, thereby analyzing its parallel complexity.

Methods

The core of the paper's contribution lies in a new characterization of when a 2-edge-colored complete graph admits an AHC. Instead of relying solely on vertex degrees, the authors introduce the concept of an "underlying digraph" derived from an "alternating factor" (a collection of vertex-disjoint alternating cycles that cover all vertices). This underlying digraph captures the relationships between these cycles.

The key insight is that the existence of an AHC is directly linked to the connectivity properties of this underlying digraph. Specifically, if the digraph is strongly connected, or if its "first component" (a specific strongly connected component) satisfies a "nice" property, then an AHC exists. This characterization is crucial because it allows for the design of a parallel algorithm.

The algorithm leverages several lemmas that describe how to "contract" alternating cycles. These contraction operations, performed in parallel, effectively reduce the number of cycles in an alternating factor. The proofs of these lemmas often involve transforming the problem into finding cycles in a related bipartite tournament, a structure that lends itself well to parallel processing. The algorithm then proceeds by iteratively contracting cycles until either a single alternating Hamiltonian cycle is found or it's determined that none exists.

Datasets

Not discussed in the paper. The problem is theoretical and deals with graph structures rather than empirical datasets.

Key Insights and Ideas

  • New Characterization: The paper's most significant contribution is the characterization of AHC existence based on the connectivity of an "underlying digraph" derived from an alternating factor. This moves beyond degree-based conditions and provides a more structural insight.
  • Cycle Contraction for Parallelism: The development of lemmas for parallelly contracting alternating cycles is key. These lemmas allow for a significant reduction in the problem's complexity in a parallel setting.
  • Bipartite Tournament Transformation: The technique of transforming the problem into finding cycles in a bipartite tournament is a powerful tool for leveraging existing parallel algorithms for such structures.
  • RNC Class Membership: By developing an efficient parallel algorithm, the paper demonstrates that the AHC problem for 2-edge-colored complete graphs belongs to the RNC complexity class, meaning it can be solved efficiently by randomized parallel algorithms.

Key Results

  • Parallel Algorithm: The paper presents a parallel algorithm for finding an AHC in a 2-edge-colored complete graph.
  • If an alternating factor is given, the algorithm runs in O(log n) time using O(n²) processors on a CRCW-PRAM.
  • If an alternating factor needs to be found first (which involves a maximum matching algorithm), the overall randomized algorithm runs in O(log³n) time using O(n⁵.5) processors.
  • Sequential Algorithm Improvement: As a byproduct of their parallel approach, the authors derive a sequential algorithm for the AHC problem with a complexity of O(n².5), which improves upon the previously best-known O(n³) sequential algorithm.

Limitations and Future Work

  • Focus on Complete Graphs: The presented algorithms and characterizations are specific to 2-edge-colored complete graphs. The problem remains NP-complete for general graphs.
  • Randomized vs. Deterministic: While a deterministic parallel algorithm is presented for the case where an alternating factor is given, finding the factor itself relies on a randomized maximum matching algorithm for the overall parallel solution.
  • Future Work: The paper implicitly suggests exploring the AHC problem in more general graph settings or with more than two colors, though these are not explicitly detailed as future research directions within the text. The improved sequential algorithm also opens avenues for further optimization.

Summary updated

BibTeX
@inproceedings{bampis1995parallel,
  author = {Evripidis Bampis and Yannis Manoussakis and Ioannis Milis},
  title = {{On the Parallel Complexity of the Alternating Hamiltonian Cycle Problem}},
  booktitle = {Combinatorics and Computer Science},
  year = {1995},
  doi = {10.1007/3-540-61576-8\_96},
}
Figure