A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
Bibliographic record
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.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.004 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.001 | 0.002 |
| Bibliometrics | 0.001 | 0.003 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.002 | 0.004 |
| Open science | 0.002 | 0.003 |
| Research integrity | 0.002 | 0.003 |
| Insufficient payload (model declined to judge) | 0.016 | 0.004 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".