The problem of covering a graph by a minimal number of vertex disjoint paths is discussed. For the class of cacti, that is, graphs where no edge lies on more than one cycle, it is shown that an algorithm solving this problem in time linear in the number of vertices exists.

This result, however, is an easy corollary from a result of my work with S. Arnborg and J. Lagergren [1] that each linear EMS extremum problem can be solved in linear time if the tree decomposition of the corresponding graphs is given. Since it is easy to see that the above path-covering problem is a linear EMS extremum problem, it remains to be shown that the tree decomposition of cacti can be found in linear time. But cacti have a tree-width of less than 2 and hence, by a result from Matousek and Thomas [2], this result follows.