An approximation algorithm for the k-fixed depots problem

•The k-DHPP, in a cubic graph with 2-vertex-connected, is studied.•We establish a new approximation algorithm (with 5/3-approximation).•A shortest tour in a factor critical and 2-vertex connected graph is considered.•A polynomial approximation algorithm (with 7/6-approximation ratio) is established.

In this paper, we consider the k-Depots Hamiltonian Path Problem (k-DHPP) of searching k paths in a graph G, starting from k fixed vertices and spanning all the vertices of G. We propose an approximation algorithm for solving the k-DHPP, where the underlying graph is cubic and 2-vertex-connected. Then, we prove the existence of a 53-approximation algorithm that gives a solution with total cost at most 53n-4k-23. In this case, the proposed method is based upon searching for a perfect matching, constructing an Eulerian graph and finally a k paths solution, following the process of removing/adding edges. We also present an approximation algorithm for finding a shortest tour passing through all vertices in a factor-critical and 2-vertex connected graph. The proposed algorithm achieves a 76-approximation ratio where the principle of the method is based on decomposing the graph into a series of ears.