Minimal Path Covering
This is only my Intuition on the problem, without any proof or explicit algorithm. This might yield an algorithm that can calculate directly the minimal path covering, or at least you might be able to use it to approximately solve the problem.

To start out, consider the simplest case: a path graph with $n$ nodes. Clearly, you will need only 2 vertices - both endpoints.
Now, lets take a look at a more complicated (and useful) graph: a cycle with $n$ nodes.
The smallest path covering must contain all nodes, since otherwise we can easily construct a path that goes through all nodes except one.
The important bit here, is that we can think of a general graph as a &quot;combination&quot; of such cycles and path graphs (any combination of such graphs with one or more nodes in common).
Basically, an idea behind trying to find the smallest path covering is to identify the cycles and paths. Then, start by &quot;marking&quot; each node at those cycles. Then using the &quot;path graphs&quot; try to identify which nodes you don't have to include (for example, think of two cycles connected by a path. Marking any node in one cycle is the same as marking the &quot;endpoint&quot; of the path graph. So the minimal path covering will mark every node that isnt in the path). Always make sure that both graphs at the endpoints of a path graph are &quot;marked&quot; (a graph is marked if any node in it is marked), as well as any graph connected to a node in a cycle is marked.
This is the basic idea of an algorithm to find which nodes we have to include in the minimal path covering. Try to refine this idea a bit more, and it will give a way to calculate or at least approximate the minimal path covering.