# Minimal disjoint chains covering graph vertex set

I'm looking for references on the following problem:

Given a graph $G=(V,E)$, what is the minimum number of simple, disjoint paths that span all the vertices in $V$?

i.e., let $P$ be the answer to this problem. Then $P$ has the following properties:

• each member $p$ of $P$ is a simple path (a chain)-- i.e., no cycles on $p$, and every node except the $2$ end nodes (they have the degree $1$ each) has degree $2$,

• for any $p_1$ and $p_2$ in $P$, there does not exist a vertex $v$ where $v$ is on both $p_1$ and $p_2$,

• there does not exist a vertex $v$ in $V$ where $v$ is not on a path $p$ that is $P$, i.e., the paths in $P$ cover the vertex set,

• there is no other such set $P'$ satisfying $|P'|<|P|$.

TIA.

//==========================

EDIT:

The graph is directed in a specific case. I'm interested in both directed and undirected cases.

• You're looking for a way to find $P$? Sep 16 '14 at 8:13
• @Snufsan no- i already solved it. looking to see its background.
– Roam
Sep 16 '14 at 14:25

## 1 Answer

This is called a minimum path cover, optimal path cover, or path partition. The number of paths in a minimum path cover is the path covering number. This paper gives quite an extensive list of references on the problem:

http://arxiv.org/pdf/1204.2306.pdf