3
$\begingroup$

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

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

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.

$\endgroup$
3
  • $\begingroup$ I think you need additional constraints to force nodes in $R$ to appear in different trees. $\endgroup$ – RobPratt Mar 27 at 22:41
  • $\begingroup$ 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? $\endgroup$ – prubin Mar 28 at 16:09
  • $\begingroup$ OK, I guess the constraints don’t enforce it but every optimal solution will satisfy it if the OP’s objective function has positive edge weights. $\endgroup$ – RobPratt Mar 28 at 17:48
4
$\begingroup$

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.

Like the usual formulation for the minimum-cost multicommodity network flow problem, this formulation lends itself to Dantzig-Wolfe decomposition with one block per commodity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.