# IP model for k-rooted spanning forest

I am looking for an IP model for finding a $$k$$-rooted minimum spanning forest on an undirected graph $$G$$.

Given a set of roots $$R$$ and a set of nodes $$N$$ $$(R\cap N=\emptyset)$$, I would find a forest of $$k=|R|$$ disjointed trees that span all nodes in $$R \cup N$$ where each $$r \in R$$ belongs to exactly one tree, and the sum of the edges in the trees is the minimum.

AFAIK, this is a well-known problem. However, I only found IP models for the (single) minimum spanning tree.

I tried to extrapolate a model from here, but to no avail (there are a few things I don't understand, and eventually my attempt does not avoid cycles).

I know that this is $$\sf NP$$-hard, but I would like to implement and test it on small instances.

Thanks

• Does $G$ contain any nodes outside of $R \cup N$? – RobPratt Mar 27 at 22:11
• @RobPratt no, $G$ does not contain any node outside $R \cup N$. – Libra Mar 27 at 22:55

There are flow models for the MST problem that can easily be adapted to the $$k$$-rooted MST. For each edge $$e=(i,j)$$ in the graph, create a binary variable $$x_e$$ (1 if the edge is used in a tree, 0 if not) and two nonnegative variables $$y_{ij}, y_{ji}$$ representing flows along the edge in either direction. Connect them via the constraints $$y_{ij} \le n x_e$$ and $$y_{ji} \le n x_e$$ where $$n = \vert N \vert$$. The objective is to minimize the weighted sum of the $$x_e$$ variables.
Add a dummy source node to $$G$$ with supply $$n$$ and an arc with cost 0 and capacity $$n$$ to each node in $$R$$. Give each node in $$N$$ a demand of 1 and set up the usual flow conservation constraints. Note that there are no costs for flows, only the fixed costs for including the edges carrying the flows.
• I think you need additional constraints to force nodes in $R$ to appear in different trees. – RobPratt Mar 27 at 22:41
• Do I? I'm assuming that every edge has strictly positive weight. So if two nodes of $r_1, r_2 \in R$ appear in a single tree, you can drop the edge connecting $r_2$ to the tree (making $r_2$ a shrub of its own), save the cost of that edge, and still have every node in the tree receiving flow from $r_1$, right? – prubin Mar 28 at 16:09
I recommend extending Paul's single-commodity formulation to a multicommodity formulation with $$k$$ commodities. Let binary variable $$z_{i,r}$$ indicate whether node $$i\in R \cup N$$ is assigned to tree $$r\in R$$. The idea is to send one unit of commodity $$r$$ from the dummy source node $$0$$ to node $$i$$ iff $$z_{i,r}=1$$. The problem is to minimize $$\sum_e c_e x_e$$ subject to \begin{align} \sum_r z_{i,r} &= 1 &&\text{for i\in R \cup N} \\ z_{r,r} &= 1 &&\text{for r\in R} \\ y_{i,j,r} + y_{j,i,r} &\le (n+1) x_e &&\text{for e=(i,j) \in E and r\in R} \\ \sum_j (y_{j,i,r} - y_{i,j,r}) &= z_{i,r} &&\text{for i \in R \cup N and r \in R} \\ \sum_j y_{0,j,r} &= \sum_i z_{i,r} &&\text{for r \in R} \\ \end{align} You can optionally include a cut $$\sum_e x_e = n$$ because a spanning forest on $$n+k$$ nodes with $$k$$ trees has $$n$$ edges.