A minimum Hamiltonian completion of a
graph G
is a minimumsize set of edges that, when added
to G, guarantee a Hamiltonian path. Finding a
Hamiltonian completion has applications to
frequency assignment as well as distributed
computing. If the new edges are deleted from the
Hamiltonian path, one is left with a
minimum path cover, a minimumsize set of
vertexdisjoint paths that cover the vertices of
G. For arbitrary graphs, constructing a minimum
Hamiltonian completion or path cover is clearly
NPhard, but there exists a lineartime
algorithm for trees. In this paper we first give
a description and proof of correctness for this
lineartime algorithm that is simpler and more
intuitive than those given previously. We show
that the algorithm extends also to unicyclic
graphs. We then give a new method for finding an
optimal path cover or Hamiltonian completion for
a tree that uses a reduction to a maximum flow
problem. In addition, we show how to extend the
reduction to construct, if possible, a covering
of the vertices of a bipartite graph with
vertexdisjoint cycles, that is, a 2factor.
