Skip to main content

Research Repository

Advanced Search

A simple polynomial algorithm for the longest path problem on cocomparability graphs

Mertzios, G.B.; Corneil, D.G.

A simple polynomial algorithm for the longest path problem on cocomparability graphs Thumbnail


Authors

D.G. Corneil



Abstract

Given a graph $G$, the longest path problem asks to compute a simple path of $G$ with the largest number of vertices. This problem is the most natural optimization version of the well-known and well-studied Hamiltonian path problem, and thus it is NP-hard on general graphs. However, in contrast to the Hamiltonian path problem, there are only a few restricted graph families, such as trees, and some small graph classes where polynomial algorithms for the longest path problem have been found. Recently it has been shown that this problem can be solved in polynomial time on interval graphs by applying dynamic programming to a characterizing ordering of the vertices of the given graph [K. Ioannidou, G. B. Mertzios, and S. D. Nikolopoulos, Algorithmica, 61 (2011), pp. 320--341], thus answering an open question. In the present paper, we provide the first polynomial algorithm for the longest path problem on a much greater class, namely on cocomparability graphs. Our algorithm uses a similar, but essentially simpler, dynamic programming approach, which is applied to a lexicographic depth first search (LDFS) characterizing ordering of the vertices of a cocomparability graph. Therefore, our results provide evidence that this general dynamic programming approach can be used in a more general setting, leading to efficient algorithms for the longest path problem on greater classes of graphs. LDFS has recently been introduced in [D. G. Corneil and R. M. Krueger, SIAM J. Discrete Math., 22 (2008), pp. 1259--1276]. Since then, a similar phenomenon of extending an existing interval graph algorithm to cocomparability graphs by using an LDFS preprocessing step has also been observed for the minimum path cover problem [D. G. Corneil, B. Dalton, and M. Habib, submitted]. Therefore, more interestingly, our results also provide evidence that cocomparability graphs present an interval graph structure when they are considered using an LDFS ordering of their vertices, which may lead to other new and more efficient combinatorial algorithms.

Journal Article Type Article
Publication Date Jul 12, 2012
Deposit Date Nov 29, 2012
Publicly Available Date Sep 8, 2014
Journal SIAM Journal on Discrete Mathematics
Print ISSN 0895-4801
Electronic ISSN 1095-7146
Publisher Society for Industrial and Applied Mathematics
Peer Reviewed Peer Reviewed
Volume 26
Issue 3
Pages 940-963
DOI https://doi.org/10.1137/100793529
Keywords Cocomparability graphs, Longest path problem, Lexicographic depth first search, Dynamic programming, Polynomial algorithm.
Public URL https://durham-repository.worktribe.com/output/1499606

Files

Published Journal Article (316 Kb)
PDF

Copyright Statement
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.






You might also like



Downloadable Citations