An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs

• Published in: Theoretical computer science 2011-09, Vol.412 (39), p.5351-5373
• Main Authors: Hung, Ruo-Wei, Chang, Maw-Shang
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Algorithms; Applied sciences; Certifying algorithms; Circular-arc graphs; Circularity; Combinatorics; Combinatorics. Ordered structures; Complexity; Computer science; control theory; systems; Exact sciences and technology; Graph theory; Graphs; Hamiltonian cycle; Information retrieval. Graph; Interval graphs; Mathematics; Miscellaneous; Path cover; Sciences and techniques of general use; Theoretical computing
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2011.06.009

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to determine whether or not a graph contains a Hamiltonian cycle. The best result for the Hamiltonian cycle problem on circular-arc graphs is an O ( n 2 log n ) -time algorithm, where n is the number of vertices of the input graph. In fact, the O ( n 2 log n ) -time algorithm can be modified as a certifying algorithm although it was published before the term certifying algorithms appeared in the literature. However, whether there exists an algorithm whose time complexity is better than O ( n 2 log n ) for solving the Hamiltonian cycle problem on circular-arc graphs has been opened for two decades. In this paper, we present an O ( Δ n ) -time certifying algorithm to solve this problem, where Δ represents the maximum degree of the input graph. The certificates provided by our algorithm can be authenticated in O ( n ) time.