# Path Covers¶

A path cover is a set of paths in a graph such that each node of the graph belongs to at least one path.

It turns out that in directed, acyclic graphs ($\text{DAGs}$), we can reduce the problem of finding a minimum path cover to the problem of finding a maximum flow in another graph.

## Node-disjoint path cover¶

In a node-disjoint path cover, each node belongs to exactly one path.

It is possible that a path does not contains any edges. (can have single node)

We can find a minimum node-disjoint path cover by constructing a [matching graph] where each node of the original graph is represented by two nodes:

A left node and a right node.

There is an edge from a left node to a right node if there is such an edge in the original graph.

In addition, the matching graph contains a source and a sink, and there are edges from the source to all left nodes and from all right nodes to the sink.

[A Maximum matching] in the resulting graph corresponds to a minimum node-disjoint path cover in the original graph.

Each edge in the maximum matching of the matching graph corresponds to an edge in the minimum node-disjoint path cover of the original graph.

Thus, the size of the minimum node-disjoint cover is $n-c$, where $n$ is the number of nodes in the original graph and $c$ is the size of the maximum matching.

## General path cover¶

A general path cover is a path cover where a node can belong to more than one path.

A minimum general path cover may be smaller than a minimum node-disjoint path cover, because a node can be used multiple times in paths.

A minimum general path cover can be found almost like a minimum node disjoint path cover.

It suffices to add some new edges to the matching graph so that there is an edge $a \rarr b$ always when there is a path from $a$ to $b$ in the original graph(possibly through several edges).

### Dilworth's Theorem¶

An antichain is a set of nodes of a graph such that there is no path from any node to another node using the edges of the graph.

Dilworth's Theorem states that in a directed acyclic graph($\text{DAGs}$), the size of a minimum general path cover equals the size of maximum antichain.