# Given a digraph and a root, find a tree that minimizes the sum of edges

Instance: a directed graph $G = (V, A)$ with weights $w_a\in\mathbb{R}$ on the edges and a root $v\in V$.
Solution: A directed tree with root $v$.
Objective: Minimize total weight.

My formulation:

My AMPL code:

param n >= 1, integer;  # number of vertices

set V := 0..n-1;
set E within {V,V};
param r := 0;

param w{E};  # edge weights

#Variável que determina se a aresta pertence a árvore
var x{V,V} binary;

#Variável que determina se existe um caminho de v pra r
var y{V} binary;

minimize maed :
sum{(u,v) in E} x[u,v] * w[u,v];

subject to UreachR {(u,v) in E} : y[u] >= x[u,v];
subject to VreachR {(u,v) in E} : y[v] >= x[u,v];
subject to rest3 {u in V : u != r} : y[u] = sum{v in V} x[v,u];


The formulation and corresponding code above is returning A subgraph of G with cycles... I want a restriction that can eliminate them (make a tree).

• Hint: Google "minimum spanning tree in directed graph", you'll come to the Chiu-Liu/Edmonds algorithm. Now think about how you could reduce the weight further by getting rid of some vertices; is it safe to do so greedily? – j_random_hacker Dec 4 '16 at 12:39