A Hamiltonian cycles (plural) problem?

Question

I'll be brief. I have a set of n vertices in a complete weighted graph, some of these vertices can be thought of as power plants and the rest as cities, and I need to find the shortest way to connect every city to a powerplant such that every vertex has degree 2; which will give some union of disjoint cycles, each including one or more power pants. This looks like a Hamiltonian cycle problem, except for the fact that I am allowed to use several components. This could be solved by considering every possible grouping of vertices and finding the Ham-cycle for each, but the Ham-cycle problem is already NP-hard, and the number of groupings is some function of n!, so its possible that the universe may end before I finish trying that. Does anyone know what this problem is called (if it has a proper name), or any papers or references I might be able to use? Thanks

Answer 1

Sounds like a "Steiner" variant of the cycle cover problem. You can solve it via integer linear programming as follows. Let binary decision variable $x_{ij}$ indicate whether edge $(i,j)$ appears among the cycles, with cost $c_{ij}$. Let binary decision variable $y_i$ indicate whether node $i$ appears among the cycles. The problem is to minimize $\sum_{i,j} c_{ij} x_{ij}$ subject to linear constraints: \begin{align} \sum_{(i,j): \text{$j$ is a power plant}} x_{ij} &\ge 1 &&\text{for all cities $i$} \tag1\label1\\ \sum_{(i,j): k \in \{i,j\}} x_{ij} &= 2 y_k &&\text{for all $k$} \tag2\label2 \end{align} Constraint \eqref{1} assigns each city to at least one power plant. Constraint \eqref{2} enforces the degree-$2$ restriction.