Minimum Path Cover in DAGs

From Separate Vertices to Connected Paths

Imagine beginning with every DAG vertex as a one-vertex path. There are $n$ paths. Whenever an edge $u\to v$ is chosen to place $v$ immediately after $u$, two paths merge and the count falls by one. The optimization question is therefore: how many compatible predecessor–successor links can we choose at once?

The Problem—and Two Variants to Keep Separate

A vertex-disjoint path cover is a collection of directed paths in which every vertex appears exactly once. Paths of one vertex are allowed. The goal is to use as few paths as possible.

Split Every Vertex, Then Match

Construct a bipartite graph with a left copy $v_L$ and a right copy $v_R$ of every DAG vertex. For each DAG edge $u\to v$, add the bipartite edge $u_L\to v_R$.

flowchart TD
    D[Copy every vertex left and right] --> E[Map each DAG edge u→v to uL→vR]
    E --> M[Find a maximum bipartite matching]
    M --> S[Matched pairs become successor links]
    S --> P[Begin at unmatched right copies and follow links]

Worked Example: From Matching to Two Paths

The example DAG has five vertices and six edges:

The matching size is $3$, so the cover size is:

Right copies $A_R$ and $C_R$ are unmatched, so reconstruction starts at $A$ and $C$. Following matched successors produces $A\to B\to D\to E$ and $C$.

Why the Formula Is $n-|M_{\max}|$

The equality follows from two directions.

From a matching to a path cover

Each matched edge chooses one successor and one predecessor. Matching constraints prevent branching: no vertex receives two chosen predecessors, and no vertex chooses two successors. Because the original graph is acyclic, the selected links form disjoint paths, not cycles. Starting from $n$ singleton paths, each of the $|M|$ selected links merges two components, leaving $n-|M|$ paths.

From a path cover to a matching

Suppose a cover has $k$ paths. A path containing $r$ vertices uses exactly $r-1$ internal edges. Summed across all paths, the cover uses $n-k$ predecessor–successor links. Those links form a valid bipartite matching, because every vertex has at most one predecessor and one successor inside its path. Therefore a maximum matching is at least $n-k$, and minimizing $k$ is equivalent to maximizing the matching.

Reconstructing the Actual Paths

A matching algorithm usually returns pairLeft[u], the right vertex matched to left copy $u_L$, or “unmatched.” Convert it into two arrays:

1. For every matched pair $u_L\to v_R$, set successor[u] = v and predecessor[v] = u.
2. Every vertex with no predecessor is a path start.
3. From each start, repeatedly follow successor until none exists.

Implementation: Reuse the Matching Result

Run Hopcroft–Karp or a simpler augmenting-path matcher first. The following code turns its left-pair array into the actual cover.

def reconstruct_path_cover(pair_left):
    n = len(pair_left)
    successor = [-1] * n
    predecessor = [-1] * n

    for u, v in enumerate(pair_left):
        if v != -1:
            successor[u] = v
            predecessor[v] = u

    paths = []
    for start in range(n):
        if predecessor[start] != -1:
            continue
        path = []
        vertex = start
        while vertex != -1:
            path.append(vertex)
            vertex = successor[vertex]
        paths.append(path)
    return paths

pair_left = [1, 3, -1, 4, -1]
print(reconstruct_path_cover(pair_left))  # [[0, 1, 3, 4], [2]]

vector<vector<int>> reconstruct(const vector<int>& pairLeft) {
    int n = pairLeft.size();
    vector<int> successor(n, -1), predecessor(n, -1);
    for (int u = 0; u < n; ++u) {
        int v = pairLeft[u];
        if (v != -1) {
            successor[u] = v;
            predecessor[v] = u;
        }
    }
    vector<vector<int>> paths;
    for (int start = 0; start < n; ++start) {
        if (predecessor[start] != -1) continue;
        vector<int> path;
        for (int v = start; v != -1; v = successor[v])
            path.push_back(v);
        paths.push_back(path);
    }
    return paths;
}

static List<List<Integer>> reconstruct(int[] pairLeft) {
    int n = pairLeft.length;
    int[] successor = new int[n], predecessor = new int[n];
    Arrays.fill(successor, -1);
    Arrays.fill(predecessor, -1);
    for (int u = 0; u < n; u++) {
        int v = pairLeft[u];
        if (v != -1) {
            successor[u] = v;
            predecessor[v] = u;
        }
    }
    List<List<Integer>> paths = new ArrayList<>();
    for (int start = 0; start < n; start++) {
        if (predecessor[start] != -1) continue;
        List<Integer> path = new ArrayList<>();
        for (int v = start; v != -1; v = successor[v])
            path.add(v);
        paths.add(path);
    }
    return paths;
}

Where Path Covers Are Useful

The reduction applies when a vertex must be used exactly once and an edge means one item may directly follow another.

Pitfalls and Boundary Cases

Complexity and Algorithm Choice

The split graph has $2n$ vertices and $m$ bipartite edges. Building it costs $O(n+m)$. Hopcroft–Karp finds a maximum matching in $O(m\sqrt{n})$ time and $O(n+m)$ memory; reconstruction adds $O(n)$. A topological-sort validation also costs $O(n+m)$.