The longest path

Overview

Kent Quanrud contrasts longest-path algorithms on directed acyclic graphs (DAGs) with the hardness of Hamiltonian path in general directed and undirected graphs. He derives a cached recurrence running in O(V+E) for DAGs, then sketches reductions from 3SAT to directed Hamiltonian path and from directed to undirected Hamiltonian path using variable ladders, clause detours, and in/out vertex gadgets. The lecture also connects Hamiltonian path to Hamiltonian cycle and shows how a general graph coin-collection problem can be reduced to a DAG problem by collapsing strongly connected components.

Key takeaways

Longest path in a DAG is computable in O(V+E): use a sink base case, recurse over outgoing edges, and cache each vertex's result.
Directed Hamiltonian path is hard because a path must cover every vertex without repetition; the 3SAT reduction encodes assignments as rung directions and clause satisfaction as mandatory detours.
A reduction proof needs both implications: every satisfying assignment must produce a Hamiltonian path, and every Hamiltonian path must yield a satisfying assignment.
Directed Hamiltonian path can be represented in an undirected graph by splitting each vertex into in- and out-copies and forcing traversal through the connecting gadget in the intended order.
The coin-collection problem allows revisits, so strongly connected components can be collected wholesale and collapsed into a DAG; this structural reduction does not work for Hamiltonian path's no-repeat constraint.
A problem on a general graph may still be tractable when its rules expose a DAG structure, as the SCC condensation does for coin collection.

Chapters

0:00 Why Simple Problems Can Encode SAT

Kent Quanrud recalls reductions linking 3SAT, Max-2SAT, and Subset Sum to illustrate how apparently simple problems can encode Boolean logic.
Subset Sum dynamic programming takes time proportional to the numeric target T, which is not polynomial in the number of bits needed to represent T.
The central lesson is that a problem's surface appearance—such as adding numbers—does not reveal whether it can represent arbitrary logical constraints.

4:02 Longest Path, Hamiltonian Path, and Three Graph Settings

The lecture asks for the longest path in a directed graph and distinguishes a path, which cannot repeat vertices, from a walk, which can.
A Hamiltonian path visits every vertex exactly once; deciding whether one exists is a yes/no version of the longest-path problem.
The three cases to compare are DAGs, general directed graphs, and undirected graphs; an algorithm for directed graphs would also apply to DAGs.

10:03 DAG Longest Walk via a Cached Recurrence

For a vertex v, define the longest-walk value as 0 when v is a sink; otherwise take the maximum of 1 plus the value at each out-neighbor.
A DAG has no cycles, so recursive subproblems cannot loop indefinitely and every reachable continuation can be evaluated.
With memoization, each vertex is solved once and its outgoing edges are scanned once overall, giving O(V+E) running time.

16:39 Why Hamiltonian Path Makes General Directed Graphs Hard

Quanrud focuses on directed Hamiltonian path: if longest path could be computed efficiently, its length would reveal whether a Hamiltonian path exists.
The reduction goal is to transform a 3SAT instance into a graph whose Hamiltonian paths correspond to satisfying assignments.
Unlike the DAG recurrence, a general graph has cycles and a Hamiltonian path must coordinate choices while preventing repeated vertices.

22:00 Variable Ladders Encode True-or-False Assignments

Each variable is represented by a bidirectional rung that a Hamiltonian path must traverse in one of two directions.
The chosen direction encodes the variable's truth value, such as left-to-right for false and right-to-left for true.
Cross-edges link successive rungs, creating a ladder that lets a path make one assignment choice for each variable while covering the graph's backbone.

27:20 Clause Vertices Become Detours Along Variable Rungs

Each clause receives a vertex that the Hamiltonian path must visit, making clause coverage part of the graph traversal.
Edges let the path detour through a clause vertex when it traverses a variable rung in a direction that satisfies a literal.
For a clause such as x1 OR NOT x2, the construction provides satisfying-direction detours for x1=true or x2=false while arranging the graph to prevent invalid backward traversal.

36:00 Proving the 3SAT-to-Hamiltonian-Path Reduction

A satisfying assignment yields a Hamiltonian path by choosing each variable rung's direction and using satisfying detours to visit clause vertices.
In the reverse direction, the gadget structure forces a Hamiltonian path into the intended rung-by-rung form, from which the variable assignment can be read.
The proof must establish both directions—satisfying assignment implies Hamiltonian path, and Hamiltonian path implies satisfying assignment—to show equivalence.
The constructed graph has roughly O(mn) vertices for m clauses and n variables, so its size remains polynomial in the formula size.

43:03 Why Undirected Hamiltonian Path Needs a New Gadget

Simply erasing arrow directions from a directed graph can create undirected Hamiltonian paths that use edges in invalid directions.
Strong connectivity does not solve the problem: mutual reachability among vertices does not guarantee a path visiting each vertex exactly once.
A successful reduction must preserve each original vertex's distinction between incoming and outgoing edges after converting the graph to undirected form.

50:05 Split Each Directed Vertex into In and Out Copies

Replace each original vertex with an in-vertex and an out-vertex, joined by a central connection that a Hamiltonian traversal must cross.
Represent each original directed edge from u to v as an undirected connection from u's out-copy to v's in-copy.
The split gadget aims to force a Hamiltonian path to enter through the in-side and leave through the out-side, preserving the direction of the original graph's edges.

56:40 Reading Hamiltonian Paths from the In-Out Construction

A directed Hamiltonian path maps into the undirected construction by passing through each vertex's in-copy, central connection, and out-copy.
For the reverse direction, show that any Hamiltonian path in the gadget must use the intended in-to-out traversal; otherwise it cannot cover all gadget vertices.
Once that structure is established, the in- and out-connections identify the original directed edges and recover a directed Hamiltonian path.

59:25 Hamiltonian Cycle and the Cost of Endpoint Choices

A Hamiltonian cycle visits every vertex exactly once and returns to its starting point, unlike a Hamiltonian path.
Choosing a start or end vertex adds only polynomially many possibilities: trying all starts costs a factor of n, and trying endpoint pairs costs at most n².
Therefore, removing endpoint choices does not by itself turn an intractable Hamiltonian-path problem into a polynomial-time one.

1:03:27 Turn Hamiltonian Path into Hamiltonian Cycle with a Supervertex

Add a new supervertex connected in both directions to every vertex of the original directed graph.
A Hamiltonian path becomes a Hamiltonian cycle by connecting its final vertex to the supervertex and the supervertex back to its first vertex.
Conversely, remove the supervertex and its two incident cycle edges to recover a Hamiltonian path through all original vertices.

1:07:10 Coin Collection on Graphs and the Hidden DAG

In the coin-collection problem, a walk may revisit vertices, but each vertex's coins are collected only once; the goal is to maximize coins gathered.
On a DAG, a recurrence adds the coins at the current vertex to the best continuation, and memoization makes the computation efficient.
For a general directed graph, strongly connected components can be collapsed into single vertices with their coin totals summed.

1:09:00 Strongly Connected Components Reduce Coin Collection to a DAG

Within a strongly connected component, reaching one vertex makes every other vertex in that component reachable, so all its coins can be collected.
Collapsing strongly connected components produces a condensation graph, which is always a DAG.
The DAG recurrence then solves the general coin-collection problem, illustrating why its walk rules differ from the no-repeated-vertex constraint in Hamiltonian path.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.