Fact-checked by Grok 2 weeks ago

Longest path problem

In graph theory, the longest path problem is the task of identifying a simple path—a sequence of distinct vertices connected by edges—of maximum length in a graph.^[1] This problem generalizes the Hamiltonian path problem, which seeks a path visiting every vertex exactly once and is a special case where the maximum length equals the number of vertices minus one.^[2] Unlike the shortest path problem, which can be solved efficiently using algorithms like Dijkstra's for non-negative weights, the longest path problem is NP-hard in general graphs, meaning no known polynomial-time algorithm exists unless P = NP.^[3] It is also inapproximable within a constant factor in polynomial time unless P = NP, as established through reductions showing that achieving any fixed approximation ratio would imply efficient solutions to NP-complete problems.^[4] Despite its hardness, the problem admits efficient solutions in restricted graph classes; for instance, in directed acyclic graphs (DAGs), it can be solved in linear time using dynamic programming after topological sorting, by computing the longest path to each vertex in reverse topological order.^[5] Similar polynomial-time algorithms exist for trees and other structured graphs. Applications include project scheduling via the critical path method and bioinformatics for sequence alignment. Research continues on parameterized complexity and exact algorithms for special graph classes.

Definition and Variants

Formal Definition

In graph theory, a simple path is defined as a sequence of distinct vertices connected by edges, with no vertex repeated, ensuring the path contains no cycles.^[6] This contrasts with a walk, which is a sequence of vertices and edges that may repeat vertices and edges; however, the longest path problem specifically considers simple paths, as repeats would permit unbounded lengths in graphs with cycles.^[6] The longest path problem is formally stated as follows: given a graph G = (V, E), either undirected or directed, find a simple path that maximizes the length, where length is measured by the number of edges in the unweighted case or by the sum of edge weights in the weighted case.^[3] Let n = |V| and m = |E| denote the number of vertices and edges, respectively; in the unweighted variant, the maximum possible length is at most n-1, while weights can be non-negative real numbers affecting the total sum.^[3] For example, in the complete graph K_n on n vertices, where every pair of distinct vertices is connected by a unique edge, the longest simple path has exactly n-1 edges, visiting all vertices without repetition.^[7] This corresponds to a Hamiltonian path, a special case of the longest path problem where the path length equals n-1.^[7]

Weighted and Unweighted Variants

The longest path problem is typically studied in its unweighted form, where the length of a path is measured by the number of edges it contains, equivalent to finding a simple path (no repeated vertices) that maximizes the number of vertices minus one.^[8] In this variant, all edges are considered to have unit weight, and the problem seeks the maximum such length in a given graph.^[3] In the weighted variant, each edge is assigned a non-negative weight, and the length of a path is defined as the sum of the weights of its edges.^[9] The goal remains to find a simple path maximizing this weighted sum. The problem applies to both undirected and directed graphs. In undirected graphs, a path can traverse edges in either direction, treating them as bidirectional.^[3] In directed graphs, paths must follow the orientation of the edges, from tail to head, preventing traversal against the direction.^[3] Related variants include the longest cycle, which seeks a closed simple path (a cycle with no repeated vertices except the start and end coinciding) of maximum length, and the longest trail, which allows no repeated edges but permits repeated vertices (a walk with no repeated edges).^[10] However, the core longest path problem emphasizes simple paths, prohibiting any vertex repetition.^[10] Inputs are typically provided as a graph representation, such as an adjacency list (listing neighbors for each vertex) or adjacency matrix (boolean or weighted matrix indicating connections), along with edge weights if applicable.^[9] Outputs may include the sequence of vertices or edges forming the path, or solely its length (number of edges in the unweighted case, or weight sum otherwise).^[9]

Computational Complexity

NP-Hardness

The decision version of the longest path problem asks whether, in a given undirected or directed graph G = (V, E) with |V| = n vertices, there exists a simple path containing at least k edges. This problem is in NP, as a nondeterministic Turing machine can guess a sequence of k+1 distinct vertices and verify in polynomial time that they form a simple path by checking adjacency for each consecutive pair and ensuring no repeats. The problem is NP-hard via a straightforward polynomial-time many-one reduction from the Hamiltonian path problem, which is known to be NP-complete. Specifically, given an instance of Hamiltonian path on graph G' with n' vertices, construct the longest path instance on the identical graph G = G' with parameter k = n'-1; a Hamiltonian path exists in G' if and only if G has a simple path of length at least k, as any longer simple path is impossible in a graph with n' vertices. This reduction requires no graph modification and sets k in constant time, preserving the input size. Thus, the decision version is NP-complete, as first cataloged by Garey and Johnson. Alternative reductions establish the same hardness for variants; for example, 3-SAT can be reduced to the longest path problem by constructing a graph where satisfying assignments correspond to long paths avoiding conflicts, though the Hamiltonian reduction suffices for the standard case. The NP-completeness holds for both undirected and directed graphs, with the directed case following similarly from the directed Hamiltonian path problem. The optimization version of the longest path problem, which seeks the maximum length of a simple path in a graph, is NP-hard. This follows because a polynomial-time algorithm for the optimization version could solve the decision version by computing the maximum length and checking if it meets or exceeds k, thereby placing the decision problem in P and implying P = NP. Consequently, unless P = NP, no polynomial-time algorithm exists for finding the longest path in general graphs. This hardness sharply contrasts with the shortest simple path problem (without negative weights), which admits efficient solutions like Dijkstra's algorithm running in O((|V| + |E|) \log |V|) time using a binary heap. In special cases, such as directed acyclic graphs, the longest path can instead be computed in linear time via topological sorting followed by dynamic programming.

Decision and Optimization Versions

The decision version of the longest path problem asks whether, given an undirected graph G = (V, E) and a positive integer k \geq 1, there exists a simple path in G of length at least k.^[11] This problem is a member of NP, as a proposed path serves as a polynomial-size certificate that can be verified in linear time by checking adjacency of consecutive vertices, absence of repeated vertices, and that the path has at least k edges.^[11] The optimization version of the longest path problem seeks to compute the maximum length of a simple path in a given graph G. The corresponding search version requires outputting such a maximum-length path. Both versions are NP-hard.^[11] The optimization version is self-reducible to the decision version: the maximum length can be found via binary search over possible values of k from 1 to |V|, requiring O(\log |V|) calls to the decision oracle, after which the search version can recover the path by iteratively querying for extensions.^[12] Regarding co-NP aspects, the complement of the decision problem—determining whether no simple path of length at least k exists in G—belongs to co-NP by definition. However, the decision problem itself is not known to lie in co-NP, since membership of an NP-complete problem in co-NP would imply that NP = co-NP.^[13]

Exact Solutions for Special Graphs

Directed Acyclic Graphs

The absence of directed cycles in a directed acyclic graph (DAG) enables the computation of a topological ordering of its vertices, which linearly arranges them such that every directed edge points from an earlier to a later vertex in the sequence. This structure facilitates an exact solution to the longest path problem via dynamic programming in linear time. First, a topological sort is performed, which can be achieved using depth-first search or Kahn's algorithm in O(n + m) time, where n is the number of vertices and m is the number of edges. Once the vertices are ordered as v_1, v_2, \dots, v_n, dynamic programming processes them sequentially: for each vertex v_i, the longest path ending at v_i is the maximum value among its predecessors u_j (with j < i) of the longest path to u_j plus the weight of the edge from u_j to v_i. Formally, define dp as the length of the longest path ending at vertex v. Then,

dp = \max_{\substack{u \to v}} \left( dp + w(u,v) \right)

if v has incoming edges, and dp = 0 otherwise (assuming unit node weights or zero for path length starting at sources). The global longest path length is the maximum dp over all vertices v. This approach handles weighted DAGs with non-negative edge weights directly; for negative weights, one could negate them and compute the shortest path using a similar dynamic programming method, though the direct longest-path formulation is generally preferred for clarity and efficiency. The overall time complexity remains O(n + m), as each edge is examined once during the dynamic programming pass. To reconstruct the actual path, track predecessor vertices during the computation, allowing backtracking from the endpoint with maximum dp to a source.

Trees and Interval Graphs

Trees, defined as undirected, connected, and acyclic graphs, admit an efficient exact solution for the longest path problem. A standard linear-time algorithm proceeds by performing two breadth-first searches (BFS). First, select an arbitrary vertex and run BFS to find the farthest vertex u. Then, run BFS from u to find the farthest vertex v. The path from u to v is a longest path in the tree, and this approach runs in O(n) time, where n is the number of vertices.^[14] For rooted trees, a dynamic programming approach computes the longest paths more explicitly. Starting from the leaves and proceeding upward to the root, the algorithm maintains for each node the length of the longest downward path from that node to a leaf in its subtree. By combining the two longest downward paths from distinct children of a node (plus the edge to the node), the longest path passing through that node can be determined. This bottom-up computation also achieves O(n) time.^[14] Interval graphs, which are the intersection graphs of intervals on the real line, form another class where the longest path problem is solvable exactly in polynomial time. These graphs possess a natural ordering of maximal cliques from left to right along the line. A dynamic programming algorithm exploits this structure by considering subpaths ending in specific cliques or intervals, building up to the global longest path in O(n^4) time.^[15] More broadly, graphs with bounded treewidth— a measure of how "tree-like" the graph is—allow exact solutions via dynamic programming on a tree decomposition of width t. The state at each bag tracks partial paths intersecting the bag, with combinations across the decomposition yielding the longest path in $2^{O(t)} n^{O(1)} time. This generalizes the tree case, where treewidth is 1.^[16] As a simple example, consider a path graph, which is a special case of a tree. Here, the longest path is the entire graph itself, spanning all n vertices in O(n) time via the above tree algorithms.^[14]

Approximation Methods

Approximation Algorithms

The longest path problem in general graphs is notoriously difficult to approximate, with no polynomial-time approximation scheme (PTAS) known, and it is hard to approximate within a factor of n^{1-\epsilon} for any constant \epsilon > 0 unless P = NP.^[17] One influential approach for finding long paths is the color-coding technique, introduced by Alon, Yuster, and Zwick in 1995. This randomized method colors the vertices of the graph with \ell colors uniformly at random, where \ell is the desired path length. It then searches for a colorful path—a path where all vertices have distinct colors—using dynamic programming over subsets of colors, which can be solved in time $2^\ell \cdot n^{O(1)}. Since any simple path of length \ell has probability at least \ell! / \ell^\ell > 1/e^\ell of being colorful, repeating the coloring O(e^\ell \log n) times ensures success with high probability. To derandomize, the method uses universal sets of colorings of size $2^{O(\ell)} \ell^{O(\log \ell)}, leading to a deterministic algorithm. Applied to the longest path problem, this yields an approximation ratio of O(n / \log n) or better by binary searching over possible path lengths and adjusting for the graph size n.^[18] Greedy heuristics provide simple, practical ways to find reasonably long paths without guarantees on optimality. One common strategy starts from an arbitrary vertex and repeatedly extends the current path by adding an unused neighbor that maximizes some local criterion, such as degree or distance, while avoiding cycles. Another variant uses iterative improvement: begin with a random path, then repeatedly replace segments with longer detours until no improvement is possible. These methods run in O(n^2) time or better and often perform well on sparse or structured graphs, though their worst-case approximation ratio can be \Omega(n).^[19] For undirected unweighted graphs, more refined algorithms achieve improved ratios. There is no PTAS, but Björklund presents an algorithm with approximation ratio O\left( \frac{n}{\log^2 n} \right), building on techniques like inclusion-exclusion and fast subset convolutions to detect long paths efficiently.^[20] In directed graphs, approximation is generally weaker due to the asymmetry. Sampling-based methods, such as selecting multiple starting vertices and computing paths from each, have been explored, but strong guarantees are limited by inapproximability results. For practical instances with small n (up to a few hundred vertices), exact methods like branch-and-bound can be effective. These explore the search tree of possible paths, pruning branches using upper bounds on remaining path length derived from graph distances or degrees. Alternatively, integer linear programming (ILP) formulations model the path as a flow with acyclicity constraints, solvable by off-the-shelf solvers like CPLEX for moderate sizes.^[21]

Inapproximability Results

The longest path problem in undirected graphs does not admit a polynomial-time approximation scheme (PTAS) unless P = NP. This follows from reductions showing that distinguishing between graphs with longest paths of length n and those with longest paths of length at most n - n^ε is NP-hard for any ε > 0. Furthermore, the problem is inapproximable within a factor of n^{1-ε} for any constant ε > 0 unless P = NP, with hardness results relying on the PCP theorem and label-cover reductions for gap amplification. These inapproximability bounds explain the failure of exact algorithms on general graphs and motivate the development of heuristics and approximations for practical instances. In directed graphs, the inapproximability is even stronger. The problem cannot be approximated within a factor of n^{1-ε} for any constant ε > 0 unless P = NP, even when the input graph is promised to contain a Hamiltonian path. Under stronger assumptions, such as NP ⊆ DTIME(n^{log log n}), the problem cannot be approximated within n / polylog n. These results also stem from PCP-based reductions and label-cover techniques. For the weighted variant with positive edge weights, similar hardness holds: there is no PTAS unless P = NP, and the inapproximability within n^{1-ε} persists, as the reductions preserve positive weights.

Parameterized Complexity

Fixed-Parameter Tractable Approaches

The longest path problem is fixed-parameter tractable when parameterized by the solution size ℓ, the length of the path. In this parameterization, algorithms exist that solve the decision version—determining whether a graph contains a simple path of length at least ℓ—in running time O(f(ℓ) · n^c) for some computable function f depending only on ℓ and constant c independent of both ℓ and n, the number of vertices in the graph. A foundational randomized fixed-parameter tractable algorithm employs the color-coding technique, introduced by Alon, Yuster, and Zwick for detecting small subgraphs including paths of prescribed length. The method randomly colors the vertices of the graph using ℓ distinct colors, such that a path of length ℓ (ℓ + 1 vertices) becomes "colorful" if its vertices receive all different colors; the probability of this event for any fixed path is at least k!/k^k \approx e^{-\ell}. To detect a colorful path, dynamic programming computes, for each vertex and each subset of colors, whether there is a colorful path ending at that vertex using exactly those colors, yielding a running time of O(2^\ell \ell^2 n) per coloring attempt. By repeating the process O(e^\ell \log n) times and using perfect hash families for derandomization, the algorithm succeeds with high probability and finds a path of exactly length ℓ in overall time O(2^\ell \ell^2 n). This can be adapted to the optimization version seeking a path of length at least ℓ by invoking the procedure for every length from 1 to ℓ. The divide-and-color technique, developed by Kneis, Mölle, Richter, and Rossmanith, refines color-coding through a recursive divide-and-conquer strategy combined with randomized partitioning. The graph's vertices are randomly bipartitioned into two roughly equal sets (black and white), and the problem is solved recursively on each induced subgraph, with paths allowed to cross the partition only in limited ways that preserve simplicity. For the longest path problem, this yields a randomized algorithm running in time O(4^\ell n), improving upon the base of the exponential in the color-coding approach; derandomization increases the runtime by a logarithmic factor. The method's success probability is high after multiple independent runs, and it extends naturally to paths of length at least ℓ.^[22] Graphs with bounded treewidth admit fixed-parameter tractable solutions for the longest path problem via monadic second-order (MSO) logic. The existence of a simple path of length at least ℓ is expressible in MSO, as it involves quantifying over sets of vertices forming a connected induced path without cycles. By Courcelle's theorem, any MSO-definable property on graphs of treewidth at most tw can be decided in time f(\text{tw}, \ell) \cdot n^{O(1)}, where the function f incorporates the parameter ℓ from the formula size; practical implementations use dynamic programming on tree decompositions to achieve this bound explicitly for path properties.^[23] Although no polynomial-size kernel is known for the longest path problem parameterized by ℓ (and none is expected unless coNP ⊆ NP/poly), preprocessing rules such as vertex reduction via sunflowers or crown decompositions can shrink large instances before applying the above algorithms. A basic illustrative approach for small fixed ℓ, underlying more efficient methods like color-coding, involves enumerating all subsets of ℓ + 1 vertices and verifying if any induces a Hamiltonian path, which runs in time O(n^{\ell + 1}) but motivates the need for exponential dependence solely on ℓ.

Parameterized Hardness

The Longest Path problem, parameterized by the solution size ℓ (the number of edges in the path), is W^[24]-hard in general directed graphs. This hardness follows from a parameterized reduction from the multicolored Clique problem, where an instance is transformed into a directed graph such that a clique of size ℓ corresponds to a path of length ℓ. The reduction preserves the parameter and ensures that the problem cannot be solved in f(ℓ) n^{O(1)} time for any computable function f unless FPT = W^[24]. The problem is also W^[24]-hard when parameterized by the clique-width of the graph, even in undirected graphs. This result is established by reductions showing that finding a path of length close to the number of vertices (equivalent to the Hamiltonian Path problem) is W^[24]-hard under this parameterization, implying the same for the general Longest Path decision version. Clique-width-bounded graphs admit efficient algorithms for many problems, but the hardness here highlights the limitation for path-related tasks, with no f(w) n^{O(1)} algorithm possible unless FPT = W^[24], where w is the clique-width. When parameterized by treewidth, the Longest Path problem is fixed-parameter tractable (FPT), running in f(w) n^{O(1)} time via dynamic programming over tree decompositions that track path endpoints and partial path configurations in each bag. However, it is not fixed-parameter tractable in some variants, such as when requiring induced or chordless paths, where W^[24]-hardness holds even for bounded treewidth. The problem is para-NP-hard when parameterized by the size of a vertex cover. For any fixed vertex cover size k, the restricted problem remains NP-hard, meaning no polynomial-time algorithm exists for each fixed k unless P = NP, and thus no FPT algorithm is possible. These hardness results collectively imply that no algorithm running in f(ℓ) n^{O(1)} time exists for the parameterized Longest Path problem unless FPT = W^[24]. Despite advances in FPT algorithms for undirected graphs parameterized by ℓ, the complexity remains open for certain restricted graph classes, such as planar graphs, where no W^[24]-hardness proof preserving planarity is known, and subexponential-time algorithms exist but full FPT status is unresolved.

Applications

Project Management and Scheduling

In project management, the Critical Path Method (CPM) models projects as directed acyclic graphs (DAGs) where vertices represent tasks and edges denote dependencies, with edge weights indicating task durations; the longest path in this graph identifies the critical path, which determines the minimum overall project duration, as any delay along it directly extends the completion time.^[25]^[26] Developed in the late 1950s for applications like plant construction, CPM enables managers to prioritize tasks on the critical path to avoid bottlenecks and optimize resource allocation.^[27] The Program Evaluation and Review Technique (PERT) extends CPM by incorporating probabilistic task durations, using expected values (often calculated as the weighted average of optimistic, most likely, and pessimistic estimates) as edge weights to compute the longest path and thus the critical path under uncertainty.^[28] Originating from U.S. Navy projects in the 1950s, PERT charts visualize these networks, highlighting the longest sequence of dependent tasks to estimate project timelines and assess risks from variability in durations.^[29] A representative example arises in construction projects, where tasks such as site preparation, foundation laying, framing, and finishing are vertices, dependencies (e.g., framing cannot precede foundation) form directed edges, and durations (e.g., 5 days for foundation) serve as weights; the longest path through this network, say totaling 45 days, sets the project's baseline schedule, ensuring timely completion by focusing efforts on critical sequences like foundation-to-roofing.^[30]^[31] Commercial software like Microsoft Project implements longest path computations to automate critical path identification and scheduling, allowing users to visualize dependencies, adjust durations, and simulate delays in DAG-based project networks for real-time management.^[32]^[33] For scenarios with limited resources, extensions such as resource-constrained longest path variants incorporate availability limits into the model, transforming the problem into a more complex optimization where the critical path accounts for both dependencies and resource leveling to minimize delays without overallocation.^[34] These approaches leverage the fact that longest paths in DAGs can be solved efficiently in linear time using topological sorting.^[35]

Bioinformatics and Network Analysis

In bioinformatics, the longest path problem finds applications in modeling complex biological processes where sequential dependencies form directed graphs, particularly in scenarios requiring the identification of maximal-length chains in acyclic structures. Although the general longest path problem is NP-hard, approximations and exact methods on directed acyclic graphs (DAGs) are employed to handle these instances efficiently.^[36] In protein folding, interaction graphs represent potential contacts or structural constraints among amino acid residues, transforming the folding challenge into finding the longest path that corresponds to a viable chain conformation respecting spatial and energetic rules. For membrane proteins, this approach models the topology by seeking the longest path in a permutation-constrained graph, enabling structure prediction through dynamic programming on the resulting DAG.^[37] A related formulation uses contact matrices where the longest trail—allowing repeated nodes—orders residues to approximate the folded structure, differing from strict paths to accommodate folding ambiguities.^[38] Genome assembly leverages overlap graphs or de Bruijn graphs derived from sequencing reads, where the longest consistent path reconstructs contiguous sequences (contigs) by maximizing coverage without contradictions from repeats or errors. In overlap-layout-consensus strategies, this equates to approximating a Hamiltonian path, but practical solvers focus on longest paths to build scaffolds, addressing gaps in fragmented assemblies.^[39] For de Bruijn graphs, while Eulerian paths are ideal for exact reconstruction, longest path heuristics handle variations in error-prone long reads, prioritizing biologically plausible sequences.^[40] Phylogenetic tree analysis employs the longest path to estimate evolutionary distances, as the path between the most divergent taxa encapsulates the maximum accumulated substitutions or changes across the tree. Reconstruction algorithms from distance matrices iteratively identify farthest pairs via longest path computations, building additive trees that reflect true evolutionary histories under minimal assumptions.^[36] This metric also informs rooting strategies, such as placing the root at the midpoint of the longest path to balance branch lengths and infer ancestral states.^[41] An illustrative example arises in metabolic pathways, often represented as DAGs where nodes are reactions or metabolites and edges denote substrate-product relations; the longest path delineates critical sequences of enzymatic steps, highlighting regulatory bottlenecks or maximal biosynthetic routes. Tools mining conserved patterns compute such paths to induce connected subgraphs, revealing evolutionarily stable chains across species.^[42]

Recent Developments

Streaming and Parallel Algorithms

In the streaming model, the longest path problem is addressed by algorithms that process graph edges in a single pass while maintaining limited working memory, making them suitable for dynamic or large-scale data arrivals. A key challenge is balancing approximation quality with space efficiency, particularly in insertion-only streams where edges are added sequentially without deletions. In 2025, Chhaya Trehan developed one-pass streaming algorithms for undirected graphs that compute an \alpha-approximation to the longest path length using \tilde{O}(n^2 / \alpha) space, applicable to both insertion-only and insertion-deletion models. These algorithms leverage random sampling and path reconstruction techniques to identify long paths with high probability, also guaranteeing paths of length at least the average degree d/3 using semi-streaming space O(n \mathrm{polylog} n). For directed graphs in the insertion-only model, the same work established a tight lower bound, showing that any (n^{1-o(1)})-approximation requires \Omega(n^2) space, nearly matching the input size.^[43] Parallel algorithms for the longest path problem focus on concurrent computation across multiple processors, often targeting special graph classes where exact solutions are feasible despite the general NP-hardness. In flow networks modeled as directed grid graphs—common in applications like hydrological modeling—Kotyra and Chabudziński introduced efficient parallel algorithms in 2023 that compute exact longest flow paths using OpenMP on multicore systems, achieving significant speedups compared to sequential methods. These implementations process flow direction data and outlet points in parallel, making them adaptable to multicore environments for handling large graph instances in big data contexts, such as network analysis in environmental simulations.^[44] A notable trade-off in these models is the approximation strength: streaming algorithms often yield weaker guarantees, such as O(\sqrt{n})-approximations under tighter space bounds (e.g., O(\sqrt{n} \mathrm{polylog} n) for sparse graphs), due to one-pass constraints and memory limits, whereas parallel approaches enable exact computations in restricted cases like directed acyclic graphs or grids. For instance, in dynamic networks where edges stream in real-time (e.g., social media interactions), streaming methods provide scalable approximations for evolving longest paths; conversely, parallel algorithms excel in static big data graphs, distributing workload to uncover precise long paths in domains like bioinformatics routing. These developments extend classical offline approximations by emphasizing resource-bounded efficiency without altering core hardness results.^[43]

Quantum and AI-Based Methods

Quantum computing offers promising avenues for tackling the longest path problem through specialized algorithms that exploit quantum superposition and interference for searching vast path spaces. A hybrid quantum algorithm, combining Grover's unstructured search with Shor's quantum Fourier transform for data reduction, has been proposed to identify the longest simple path in a graph. This approach iteratively reduces the search space by factoring path length constraints and applies Grover's quadratic speedup to candidate paths, achieving theoretical efficiency improvements over classical exhaustive search for graphs with up to moderate sizes. The method encodes paths as binary strings and uses quantum parallelism to evaluate multiple candidates simultaneously, though practical implementation requires fault-tolerant quantum hardware due to the problem's NP-hard nature.^[45] Another quantum strategy reformulates the longest path problem as a quadratic unconstrained binary optimization (QUBO) instance, suitable for solving via quantum annealing on devices like D-Wave processors. In this encoding, binary variables represent edge selections in a path, with the objective function maximizing the number of selected edges while enforcing acyclicity and connectivity constraints through quadratic penalties. McCollum, Krauss, and Williamson developed QUBO formulations that minimize variable dependence on path length. These formulations are suitable for heuristic optimization in real-world applications like routing.^[3] Related quantum techniques address variants of the longest path, such as the longest trail (edge-nonrepeating path), using quantum algorithms. Khadiev and Kapralov presented an algorithm for the longest trail problem with running time O^*(1.728^m), where m is the number of edges. While not directly solving the simple longest path, it informs hybrid quantum-classical solvers for denser graphs.^[46] Artificial intelligence methods, particularly reinforcement learning (RL), are emerging for approximating longest paths in complex graphs where exact solutions are intractable. RL agents learn policies to extend paths greedily while avoiding cycles, trained via rewards proportional to path length and penalties for repetitions. Strasser's work applies RL to generate graphs with prescribed longest path lengths, using policy gradient methods to optimize over graph constructions; experiments on random graphs up to 50 vertices achieved near-optimal paths in 80% of cases after 10^5 training episodes. This approach demonstrates RL's utility in heuristic exploration, scalable to larger instances via neural network approximations of value functions.^[47] Graph neural networks (GNNs) complement RL by embedding graph structures to predict promising path extensions. In genome assembly, where de Bruijn graphs model overlaps and longest paths reconstruct sequences, GNNs like graph convolutional networks learn node embeddings to prioritize high-degree paths. Bresson et al. used GatedGCNs to predict edges in assembly graphs, improving contig lengths and genome fraction over heuristics like Raven on human genome data with PacBio HiFi reads. These AI techniques prioritize conceptual scalability, often outperforming traditional heuristics on noisy or large-scale data without exhaustive enumeration.^[48]

References

[1]
[PDF] Approximating Longest Directed Paths and Cycles
Abstract. We investigate the hardness of approximating the longest path and the longest cycle in directed graphs on n vertices.
[2]
[PDF] HAMILTONICITY AND LONGEST PATH PROBLEM ON SPECIAL ...
The longest path problem is the problem of finding a simple path of maximum length in a graph. It is easy to see that Hamiltonian Path problem is a special ...
[3]
QUBO formulations of the longest path problem - ScienceDirect.com
Apr 8, 2021 · The longest path problem on graphs is an NP-hard optimization problem, and as such, it is not known to have an efficient classical solution ...
[4]
On approximating the longest path in a graph | Algorithmica
Jul 25, 1995 · We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ...
[5]
[PDF] Dynamic Programming Longest Path in a DAG - Washington
The goal is to find the longest path in a DAG, which is a directed graph with no cycles. Dynamic programming uses topological sorting for ordering.
[6]
[PDF] Longest paths in circular arc graphs - The University of Memphis
We show that all maximum length paths in a connected circular arc graph have non–empty intersection. Keywords: interval graph, circular arc graph, maximum ...
[7]
[PDF] PATHS IN GRAPHS
A circuit is a path whose start and end vertices are the same. A path is called simple if no vertex appears on it more than once. A circuit is called simple if ...
[8]
A Simple Polynomial Algorithm for the Longest Path Problem on ...
Given a graph 𝐺 , the longest path problem asks to compute a simple path of 𝐺 with the largest number of vertices. This problem is the most natural ...
[9]
[PDF] Intersecting longest paths and longest cycles: A survey
This is a survey of results obtained during the last 45 years regarding the intersection behaviour of all longest paths, or all longest cycles, in connected ...
[10]
None
### Definition of the Longest Simple Path Problem in Undirected Weighted Graphs
[11]
[PDF] Walks, trails, paths, and cycles - Combinatorics and Graph Theory
A circuit with no repeated vertex is called a cycle. The length of a walk trail, path or cycle is its number of edges. 1 ...
[12]
[PDF] Appendix A Graph Problems - DSpace
LONG PATH [ND29]. Instance: A graph G = (V,E), an integer k 1. Question: Does G have a path of length at least k? The corresponding maximization problem is ...
[13]
[PDF] CSC 373 Lecture # 11 Instructor: Milad Eftekhar Self-reducibility
Optimization problems can also be polytime self-reducible by using decision problem algorithm to find optimal value of relevant parameter(s). Example: MAX ...
[14]
[PDF] 1 coNP and good characterizations In these lecture notes we ...
Therefore, P = NP also implies that P = coNP. The following lemma shows that NP-complete problems cannot have polynomial-length refutations unless NP = coNP.
[15]
Efficient Algorithms for the Longest Path Problem - SpringerLink
Download book PDF · Algorithms and Computation (ISAAC 2004). Efficient Algorithms for the Longest Path Problem. Download book PDF. Ryuhei Uehara &; Yushi Uno.
[16]
The Longest Path Problem has a Polynomial Solution on Interval ...
May 12, 2010 · Abstract. The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are ...Missing: DAG | Show results with:DAG
[17]
[PDF] Parameterized Algorithms - mimuw
Jan 4, 2023 · First, the book serves as an introduction to the field of parameterized algorithms and complexity accessible to graduate students and advanced ...
[18]
Approximating Longest Directed Paths and Cycles - SpringerLink
With a recent algorithm for undirected graphs by Gabow, this shows that long paths and cycles are harder to find in directed graphs than in undirected graphs.
[19]
Color-coding | Journal of the ACM
Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs · Linear time low tree-width partitions and algorithmic ...Missing: technique | Show results with:technique
[20]
[1209.2503] A greedy approximation algorithm for the longest path ...
Sep 12, 2012 · Motivated by finding a simple, quick algorithm for finding long paths in large graphs, in this paper we show a greedy algorithm with a time ...Missing: heuristics | Show results with:heuristics
[21]
[PDF] Approximating Longest Path Björklund, Andreas
The best polynomial time approximation algorithm for longest path in undi- rected graphs known to date, to the best of my knowledge, is the one presented in §2 ...
[22]
[PDF] Finding Optimal Longest Paths by Dynamic Programming in Parallel
Abstract. We propose an exact algorithm for solving the longest sim- ple path problem between two given vertices in undirected weighted graphs.
[23]
https://www.lirmm.fr/~sau/talks/LAGOS-2019-Ignasi.pdf
[24]
The ABCs of the Critical Path Method - Harvard Business Review
A powerful but basically simple technique for analyzing, planning, and scheduling large, complex projects.
[25]
CPM.java - Algorithms, 4th Edition
... problem * via the <em>critical path method</em>. It reduces the problem * to the longest-paths problem in edge-weighted DAGs. * It builds an edge-weighted ...<|separator|>
[26]
[PDF] The Critical Path
The critical path is the longest route in time for a series of related activities, helping to determine the most time-consuming path.
[27]
PERT - ProjectManagement.com
Mar 27, 2015 · The critical path is determined by adding the times for the activities in each sequence and determining the longest path in the project. The ...
[28]
PERT in Project Management: Visually Tracking Tasks
Mar 18, 2022 · PERT charts help determine timelines, establish priorities, and identify potential roadblocks. Learn how to construct a PERT chart.
[29]
10. Fundamental Scheduling Procedures
[5] The difficulty of the resource constrained project scheduling problem arises from the combinatorial explosion of different resource assignments which ...
[30]
Critical Path Method for construction: What you need to know
Oct 18, 2023 · Ergo, the critical path is the longest possible path through the web or matrix of construction activities. The entirety of the critical path ...
[31]
Show the critical path of your project in Project - Microsoft Support
View the critical path in a master project · Choose File > Options. · Choose Schedule, and then scroll down to the Calculation options for this project area.
[32]
[PDF] MICROSOFT PROJECT CRITICAL PATH CALCULATIONS
The aim of this paper is to explain how the Microsoft Project default Options affect the calculation of the Critical Path of a. Microsoft Project schedule and ...
[33]
Project scheduling with resource constraints: A branch and bound ...
This paper describes a branch and bound algorithm for project scheduling with resource constraints.
[34]
Longest Path in a Directed Acyclic Graph - GeeksforGeeks
Jul 23, 2025 · In fact, the Longest Path problem is NP-Hard for a general graph. However, the longest path problem has a linear time solution for directed ...
[35]
On the longest path algorithm for reconstructing trees from distance ...
According to their analysis, it runs in time O ( d n log d n ) for topological trees. However, this turns out to be false; we show that the algorithm takes ...Missing: problem phylogenetic
[36]
A graph-theoretic approach for classification and structure prediction ...
Since the graph is a DAG, the longest path problem is solved with a well known dynamic programming scheme [34] of complexity O ( | V | ) in space and O ...
[37]
Ordering Protein Contact Matrices - ScienceDirect.com
In graph theory, the longest trail problem is different from the longest path problem, as the path may display repeated nodes [29], as illustrated in Fig. 1b.
[38]
Algorithms for Big Data Problems in de Novo Genome Assembly
Jan 18, 2023 · The construction of large parts of the genome, called contigs, can be modelled as the longest path problem or the Euler tour problem in some ...
[39]
[PDF] Global Optimization for Scaffolding and Completing Genome ...
... genome sequence in one large sequence ... longest path problem allows one to solve simultaneously all subtasks specific for completing the genome assembly.
[40]
Minimum variance rooting of phylogenetic trees and implications for ...
In this paper, we introduce a new method of rooting a tree based on its branch length distribution; our method, which minimizes the variance of root to tip ...
[41]
[PDF] Infection Spreading and Source Identification: A Hide and ... - arXiv
may start to spread a false rumor about the company on a social network. ... longest path problem in a weighted graph, which ... Tardos, “Maximizing the spread of ...
[42]
Stochastic approximation algorithms for rumor source inference on ...
We also show that no polynomial time algorithm can find a constant factor approximation to the longest path problem unless P=NP. Finally, it is shown that ...
[43]
CoMetGeNe: mining conserved neighborhood patterns in metabolic ...
Jan 10, 2019 · Fertin et al. [23] proposed a heuristic for determining a longest path P in a directed acyclic graph (DAG) such that P induces a connected ...
[44]
Constructing Long Paths in Graph Streams
### Summary of Key Results on Streaming Algorithms for Longest Path Problem (2025 ESA Paper)
[45]
ATAM, Advances in Theoretical and Applied Mathematics ...
Volume 15 Number 1 (2020). CONTENTS. Quantum Algorithm for Longest Path Problem by Hybrid Method of Grover's Database Search and Shor's Data Decrease
[46]
[2112.13847] Quantum Algorithm for the Longest Trail Problem - arXiv
Dec 27, 2021 · We present the quantum algorithm for the Longest Trail Problem. The problem is to search the longest edge-simple path for a graph with n vertexes and m edges.
[47]
Solving the longest path problem with Artificial Intelligence
Jan 7, 2025 · The longest path problem involves finding routes with no repeated stops, using AI's reinforcement learning, which can be time-consuming for ...
[48]
[PDF] Learning to Untangle Genome Assembly with Graph Convolutional ...
Feb 27, 2023 · The problem is equivalent to the longest path problem on graphs, i.e. finding the longest path ... Graph Neural Network Model, IEEE Transactions ...