Capacitated Facility Location Problem on tree-like graphs

We consider the network Capacitated Facility Location Problem (CFLP) and its special case — the Uniform Capacitated Facility Location Problem (UCFLP), where all facilities have the same capacity. We show that the UCFLP on a star graph is linear-time solvable if every vertex of the star can be either a facility or a client but not both. We further prove that the UCFLP on a star graph is $\mathcal{NP}$-hard if the facilities and clients can be located at each vertex of the graph. The UCFLP on a path graph is known to be polynomially solvable. We give a version of the known dynamic programming algorithm for this problem with the improved time complexity $\mathcal O(m^2n^2)$, where $m$ is the number of facilities and $n$ is the number of clients. For the CFLP on a path graph we propose a pseudo-polynomial time algorithm based on the work of Mirchandani et al. (1996) with improved time complexity $\mathcal O(mB)$, where $B$ is the total demand of the clients.