⟨ Blog
The Relationship Between Path Cover and Chain Cover

A mathematician is a person who can find analogies between theorems; a better mathematician is one who can see analogies between proofs and the best mathematician can notice analogies between theories. One can imagine that the ultimate mathematician is one who can see analogies between analogies.
Stefan Banach

Path Cover

Given a simple directed acyclic graph $G=(\mathcal{V}, \mathcal{E})$, a path cover is a set of vertex-disjoint paths with their union equal to $\mathcal{V}$. Here is a more formal definition.

A path cover of $G=(\mathcal{V}, \mathcal{E})$ is a set of paths $\mathcal{PC}=\lbrace P_1,P_2,\ldots, P_k \rbrace$ where every $P_i$ is a valid path of $G$, and for any $v\in\mathcal{V}$ there exist an $i\in[k]$ such that $v\in P_i$ and $v\notin P_j$ for all $j\neq i$.

In other words, if we denote the set of vertices in $P_i$ by $\mathcal{P}_i$, we can observe that $\lbrace \mathcal{P}_1,\mathcal{P}_2,\ldots, \mathcal{P}_k \rbrace$ is a partion of $\mathcal{V}$. By definition, we can see $\lbrace (v):v\in\mathcal{V} \rbrace$ is a trivial path cover with size of $\vert \mathcal{V}\vert$. By “merging” some paths we can make the size smaller, thus there exist a (may not only) path cover with minimum size. Our question is how to find a minimum path cover? Since we don’t care about the order of vertices in a certain path of the path cover, we view $\lbrace \mathcal{P}_1,\mathcal{P}_2,\ldots, \mathcal{P}_k \rbrace$ also as a path cover only if the vertices in every $\mathcal{P}_i$ can form a valid path.

Greedily choosing the longest path whenever possible does not seem to be correct. Fewer paths do not necessarily mean longer path lengths. Here, we have some useful observations:

  1. If $\mathcal{PC}$ is a valid path cover with size $k$, which means there are $k$ vertex-disjoint paths. Let $l$ be the number of edges covered by $\mathcal{PC}$, then $k+l=n$1.

  2. For any vertex $v\in \mathcal{P}_i$, there are most one vertex $u\in\mathcal{P}_i$ such that $\lbrace u,v\rbrace\in\mathcal{E}$ or $\lbrace v,u\rbrace\in\mathcal{E}$.

Thus, we can split $v$ into two nodes, $v_{\text{out}}$ and $v_{\text{in}}$, thereby constructing a new graph $G’ = (\mathcal{V}’, \mathcal{E}’)$ such that

\[\begin{cases} \mathcal{V}'=\lbrace v_{\text{out}}:v\in \mathcal{V}\rbrace \cup \lbrace v_{\text{in}}:v\in \mathcal{V}\rbrace,\\ \mathcal{E}'=\lbrace \lbrace v_{\text{out}},u_{\text{in}}\rbrace: \lbrace v,u\rbrace \in\mathcal{E}\rbrace. \end{cases}\]

It’s obvious to see that $G’$ is a bipartite graph, and every time we find a matching $M$ with size $l$. Then, by merging $v_{\text{out}}$ and $v_{\text{in}}$ and connecting the vertices using the edges in the matching, we obtain a path cover of $G$ with size $n-l$. Therefore, we can reduce this problem to the bipartite graph matching problem / maximum flow problem.

Chain Cover

The problem we face with the chain cover is slightly different. Every two vertices in a chain only need to satisfy that one of them can reach the other.

A chain cover of $G=(\mathcal{V}, \mathcal{E})$ is a set of chains $\mathcal{CC}=\lbrace \mathcal{C}_1,\mathcal{C}_2,\ldots, \mathcal{C}_k \rbrace$ where every $\mathcal{C}_i$ is a valid chain of $G$, which means for all distinct $v, u\in \mathcal{C}_i$, there exists a path from $v$ to $u$ or from $u$ to $v$. A cover means that $\mathcal{CC}$ is a partition of $\mathcal{V}$.

NOTE: Still working on it (yes, I know, I’m lazy…).

  1. For simplicity, we denote $\vert \mathcal{V}\vert,\vert \mathcal{E}\vert$ by $n,m$, respectively. ↩