The Longest Path Problem Is Polynomial on Cocomparability Graphs
The Longest Path Problem Is Polynomial on Cocomparability Graphs
复制标题
DOI：
10.1007/s00453-011-9583-5
复制
发表时间：
2010-06
期刊：
影响因子：
1.1
通讯作者：
Kyriaki Ioannidou;Stavros D. Nikolopoulos
中科院分区：
文献类型：
--
作者：
Kyriaki Ioannidou;Stavros D. Nikolopoulos
最长路问题是在一个图中寻找一条最长的路的问题。作为哈密尔顿路问题的推广，它在一般图上是NP-完全的，事实上，在每一类图上哈密尔顿路问题都是NP-完全的。最长路问题的多项式解最近被提出用于加权树、托勒密图、二部置换图、区间图和一些小类图。虽然在近二十年前证明了上可比较图上的Hamilton路问题是多项式的，但上可比较图上的最长路问题的复杂性状态仍然是开放的;实际上，即使在较小的置换图类上，问题的复杂性状态也仍然是开放的。本文提出了一个多项式时间算法来求解一类可比较图的最长路问题。我们的结果解决了这类图的问题的复杂性的公开问题，并由于上可比图形成了一个超类的区间图和置换图，扩展了多项式的解决方案的最长路径问题的区间图和置换图类的多项式解决方案。
The longest path problem is the problem of finding a path of maximum length in a graph. As a generalization of the Hamiltonian path problem, it is NP-complete on general graphs and, in fact, on every class of graphs that the Hamiltonian path problem is NP-complete. Polynomial solutions for the longest path problem have recently been proposed for weighted trees, Ptolemaic graphs, bipartite permutation graphs, interval graphs, and some small classes of graphs. Although the Hamiltonian path problem on cocomparability graphs was proved to be polynomial almost two decades ago, the complexity status of the longest path problem on cocomparability graphs has remained open; actually, the complexity status of the problem has remained open even on the smaller class of permutation graphs. In this paper, we present a polynomial-time algorithm for solving the longest path problem on the class of cocomparability graphs. Our result resolves the open question for the complexity of the problem on such graphs, and since cocomparability graphs form a superclass of both interval and permutation graphs, extends the polynomial solution of the longest path problem on interval graphs and provides polynomial solution to the class of permutation graphs.