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|$.




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

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

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:



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.