Longest Path

Given an undirected graph $G=(V,E)$ , a simple path is a sequence of vertices

P=(v_0,v_1,\ldots,v_k)

such that every consecutive pair of vertices is connected by an edge and no vertex appears more than once.

More formally,

(v_i,v_{i+1}) \in E

for every $0 \le i < k$ , and the vertices $v_0,v_1,\ldots,v_k$ are all distinct.

The length of a path is the number of edges it contains. Therefore, the path above has length $k$ .

The goal of Longest Path is to find a simple path containing the largest possible number of edges.

Throughout this specification, Longest Path is abbreviated LP.

Before implementing your algorithms, review the project-wide Program Interface and Input Files specifications.

Graph Assumptions

LP instances use simple, unweighted, undirected graphs.

Vertices are numbered consecutively beginning with 0: $V=\{0,1,\ldots,n-1\}$ .
Graphs are not necessarily connected.
Isolated vertices may appear.
A path may begin and end at any vertices in the graph.
A vertex may appear at most once in a valid path.

The standard unweighted graph formats and supplied input routines are described on the Input Files page.

Example

The same graph and its edge-list representation are shown side-by-side below.

Example graph                                  example-01.txt

0 ------- 1 ------- 2 ------- 3                    5 5
           \       /                               0 1
            \     /                                1 2
              4                                    2 3
                                                   1 4
                                                   2 4

One valid path is

0,1,4,2,3.

It uses four edges:

(0,1),\quad (1,4),\quad (4,2),\quad (2,3).

Because the graph contains five vertices, no simple path can contain more than four edges. Therefore, this path is a longest path.

For comparison,

0,1,2,3

is also a valid path, but it has length 3 and is therefore not optimal for this instance.

The sequence

0,1,4,1,2

is not a valid simple path because vertex 1 appears more than once.

LP Solution Format

LP uses longest_path as its project-wide problem identifier. The short command-line alias is lp.

The solution dictionary contains the vertices in the reported path and its length:

{
  "length": 4,
  "vertices": [0, 1, 4, 2, 3]
}

The vertices list gives the vertices in path order. Therefore, unlike a set of vertices, the order of this list is significant.

No vertex may appear more than once. Consecutive entries in the list must be connected by an edge in the graph.

For a nonempty path,

\texttt{length} = |\texttt{vertices}| - 1.

A path consisting of a single vertex is valid and has length 0.

Using the common project interface,

python src/solve.py example-01.txt \
    --problem lp \
    --algorithm exhaustive

could produce a solution containing the path shown above.

Your program is required to report only one longest path. If an instance has multiple longest paths, any one of them is acceptable; your program does not need to enumerate all optimal solutions.

A path and the same path written in reverse order represent the same undirected path. For example,

[0,1,4,2,3]

and

[3,2,4,1,0]

are equivalent solutions.

Solution Verifier

Your Checkpoint 2 implementation must provide:

from course.common.graph import Graph


def is_valid_path(graph: Graph, vertices: list[int], k: int) -> bool:
    ...

in:

src/student/problems/longest_path/verifier.py

This is the verifier for the decision version of Longest Path. It returns True exactly when vertices is a valid simple path in graph whose length is at least k.

For the example graph:

is_valid_path(graph, [0, 1, 4, 2, 3], 4)   # True
is_valid_path(graph, [0, 1, 4, 2, 3], 5)   # False
is_valid_path(graph, [0, 1, 4, 1, 2], 3)   # False: repeated vertex
is_valid_path(graph, [0, 4, 2], 2)         # False: (0,4) is not an edge

The verifier checks the supplied certificate. It does not determine whether that path is optimal and must not call one of the solving algorithms.

Gradescope may import and test is_valid_path() independently of src/solve.py.

Checkpoint 2 Exhaustive Baseline

Checkpoint 2 uses the project-wide complete-candidate enumeration model. For Longest Path, a complete candidate is an ordered sequence of distinct vertices.

A natural exact baseline considers longer candidate sequences before shorter ones and sends each complete candidate to is_valid_path(). Once a valid candidate of a given length is found, that path is optimal because all longer candidate lengths have already been exhausted.

The Checkpoint 2 baseline should not use recursive path extension, fail-early rejection of partial candidates, branch-and-bound, or other pruning techniques. Those are precisely the kinds of improvements explored beginning in Checkpoint 3.

Checkpoint 3 Upper Bound

Longest Path is a maximization problem, so the required polynomial-time bound is an upper bound on the optimal path length:

from course.common.graph import Graph


def upper_bound(graph: Graph) -> int:
    ...

in:

src/student/problems/longest_path/bound.py

If the optimum is $OPT$ , a valid result must satisfy

OPT \le \texttt{upper\_bound}(G).

A bound may be loose, but it should provide useful information beyond blindly returning a very large number. The public tests include disconnected graphs so that you can test whether your bound takes basic graph structure into account.

Course Benchmark Suites

The supplied Longest Path benchmark manifest is located at:

benchmarks/longest_path/manifest.json

The required suites are run with the common experiment tool, for example:

python tools/run_experiments.py --suite exact_frontier
python tools/run_experiments.py --suite quality_known
python tools/run_experiments.py --suite heuristic_scale
python tools/run_experiments.py --suite structure

Exact frontier

The exact-search frontier contains three families with known optima:

three-arm trees — sparse graphs with very limited valid path extensions;
imbalanced complete bipartite graphs — connected graphs with many choices but no Hamiltonian path when the two parts differ by more than one; and
two disconnected cliques — dense local structure combined with a global connectivity restriction.

The default local exact-frontier timeout is 15 minutes per algorithm/instance. After an algorithm times out on one member of a frontier family, larger members of that same family are skipped for that algorithm.

The Gradescope timeout is intentionally shorter. Gradescope is a bounded automated check; the local CP4 frontier is where you investigate when your exact algorithm becomes impractical.

Structural experiment

The required structural study holds the graph size fixed at 300 vertices and varies the probability of adding extra edges. Every instance contains a hidden, randomly labeled Hamiltonian path, so the optimum is always 299. This lets you study the effect of edge density without simultaneously changing graph size or the optimal objective value.

See:

benchmarks/longest_path/structure.md

for the full description.