Carpathian 2006 22 129 135 [627938]

CARPATHIAN J. MATH.
22(2006), No. 1 – 2, 129 – 135
At least version of the generalized minimum
spanning tree problem
PETRIC ˘AC. P OP,ANDREI HORVAT MARC and C ORINA POPSITAR
ABSTRACT .We consider the at least version of the Generalized Minimum Spanning Tree Problem,
denoted by L-GMST, which consists in finding a minimum cost tree spanning at least one node fromeach node set of a complete graph with the nodes partitioned into a given number of node sets. Wedescribe new integer programming formulations of the L-GMST problem and establish relationshipsbetween the polytopes corresponding to their linear relaxations.
1. I NTRODUCTION
The minimum spanning tree (MST) problem can be generalized in a natural
way by considering instead of nodes, node sets (clusters) and asking for a mini-
mum cost tree spanning exactly one node from each cluster. This problem is called
the generalized minimum spanning tree problem (GMSTP) and it was introduced
by Myung et al. [4].
Meanwhile, the GMSTP have been studied by several authors w.r.t. heuristics
and metaheuristics, LP-relaxations, polyhedral aspects and approximability, cf.,
e.g. Feremans, Labbe, and Laporte [3], Feremans [2], Pop, Kern and Still [8, 9]
and Pop [5, 6].
Two variants of the generalized minimum spanning tree problem were consid-
ered in the literature: one in which in addition to the cost attached to the edges,
we have costs attached also to the nodes, called the prize collecting generalized min-
imum spanning tree problem see [7] and the second one which consists in finding
a minimum cost tree spanning at least one node from each cluster, denoted by
L-GMST and introduced by Dror et al. [1].
Dror et al. [1] showed that the L-GMST problem is NP-hard, introduced three
integer programming formulations, two of them have been proved later thatthere are invalid (see [2]) and examined a number of the heuristic solutions for
the problem.
The aim of this paper is to describe new integer programming formulations
of the L-GMST problem and establish relationships between the polytopes corre-
sponding to their linear relaxations.
2. D
EFINITION OF THE PROBLEM
The at least version of the generalized minimum spanning tree problem (L-
GMST) is defined on an undirected graph G=(V,E)with nodes partitioned into
Received: 25.03.2006; In revised form: 05.06.2006; Accepted: 01.11.2006
2000 Mathematics Subject Classification: 05C05, 68R10, 90C05, 90C10, 90C27, 90C39.
Key words and phrases: Minimum spanning tree, generalized minimum spanning trees, integer pro-
gramming, linear relaxation.
129

130 P. C. Pop, A. Horvat-Marc, Corina Pop Sitar
V1 V2 V3
V4 V5
FIGURE 1. Example of a feasible solution of the L-GMST prob-
lem, where at least one node from each cluster is selected from
each cluster
mclusters. Let |V|=nandK={1,2,…,m }be the index set of the node sets
(clusters). Then, V=V1∪V2∪…∪VmandVl∩Vk=∅for all l,k∈Ksuch that
l/negationslash=k. We assume that the graph Gis complete and each edge e={i,j}∈Ehas
a nonnegative cost denoted by cij.
The L-GMST problem is the problem of finding a minimum-cost tree spanning
a subset of nodes which includes at least one node from each cluster.
3. I NTEGER PROGRAMMING FORMULATIONS
The L-GMST problem can be formulated as an integer program in many dif-
ferent ways. For example, introducing the variables xe∈{0,1},e∈Eand
yi∈{0,1},i∈V, to indicate whether an edge/primee/primerespectively a node/primei/primeis con-
tained in the spanning tree, a feasible solution to the L-GMST problem can be
seen as a cycle free subgraph, at least one node selected from every cluster and
connecting all the clusters. Therefore the L-GMST problem can be formulated as
the following 0-1 integer programming problem:
min/summationdisplay
e∈Ecexe
s.t. y (Vk)≥1, ∀k∈K={1, …, m } (3.1)
x(E(S))≤y(S−i),∀i∈S⊂V,2≤|S|≤n−1 (3.2)
x(E)=y(V)−1 (3.3)
xe∈{0,1}, ∀e∈E (3.4)
yi∈{0,1}, ∀i∈V. (3.5)
where for S⊆V, the set of edges with both end points from S, denoted by E(S),
is defined as usually:
E(S)={e=(i,j)∈E|i,j∈S}.

At least version of the GMSTP 131
In the above formulation, we use the standard shorthand notations:
x(F)=/summationdisplay
e∈Fxe,F⊆Eandy(S)=/summationdisplay
i∈Syi,S⊆V.
For simplicity we used the notation S−iinstead of S\{i}. In the above
formulation, constraints (3.1) guarantee that from every cluster we select at leastone node, constraints (3.2) eliminate all the subtours and finally constraint (3.3)
guarantees that the selected subgraph has y(V)−1edges.
This formulation, introduced by Feremans et al., is called the generalized subtour
elimination formulation since constraints (3.2) eliminate all the cycles.
We denote the feasible set of the linear programming relaxation of this formu-
lation by P
sub, where we replace the constraints (3.4) and (3.5) by 0≤xe,yi≤1,
for all e∈Eandi∈V.
We may replace the subtour elimination constraints (3.2) by connectivity con-
straints, resulting in the so-called generalized cutset formulation :
min/summationdisplay
e∈Ecexe
s.t. (3.1),(3.3),(3.4),(3.5)and
x(δ(S))≥yi+yj−1,∀i∈S⊂V,j /∈S (3.6)
where for S⊆V, the cutset , denoted by δ(S), is defined as usually:
δ(S)={e=(i,j)∈E|i∈S, j /∈S}.
We denote the feasible set of the linear programming relaxation of this formu-
lation by Pcut. The following property holds:
Proposition 3.1. Psub⊂Pcut.
Proof. Let(x, y)∈Psubandi∈S⊂Vandj/∈S. Since E=E(S)∪δ(S)∪E(V\S),
we get
x(δ(S)) = x(E)−x(E(S))−x(E(V\S))
≥y(V)−1−y(S)+yi−z(V\S)+yj=yi+yj−1.
/square
Our next model, the so-called generalized multicut formulation , is obtained by re-
placing simple cutsets by multicuts. Given a partition of the nodes V=C0∪C1∪
…∪Ck, we define the multicut δ(C0,C1, …, C k)to be the set of edges connect-
ing different CiandCj. The generalized multicut formulation for the L-GMST
problem is:
min/summationdisplay
e∈Ecexe
s.t. (3.1),(3.3),(3.4),(3.5)and
x(δ(C0,C1, …, C k))≥k/summationdisplay
j=0yij−1,∀C0,C1, …, C knode partitions
ofVand∀ij∈Cjforj=0,1, …, k. (3.7)

132 P. C. Pop, A. Horvat-Marc, Corina Pop Sitar
LetPmcut denote the feasible set of the linear programming relaxation of this
model. Clearly, Pmcut⊆Pcut.
Proposition 3.2. Psub=Pmcut .
Proof. It suffices to prove that Psub⊆Pmcut andPmcut⊆Psub. This boils down
to showing that a pair (x, y)satisfies constraint (3.2) if and only if it satisfies con-
straint (3.7).
Let(x, z)∈PsubandC0,C1, …, C qbe a partition of the nodes. Since E=
E(C0)∪E(C1)∪…∪E(Cq)∪δ(C0,C1, …, C q), we get
x(δ(C0,C1, …, C q)) = x(E)−x(E(C0))−x(E(C1))−…−x(E(Cq))≥
≥y(V)−1−y(C0)+yi0−y(C1)+yi1−…−y(Cq)+yiq
=q/summationdisplay
j=0yij−1
where ij∈Cj,j=0,1, …, q .
Conversely, let (x, y)∈Pmcut ,i∈S⊂Vand consider the inequality (3.7)
withC0=Sand with C1, …, C kas singletons whose union is V\S. Then
x(δ(S, C 1, …, C k))≥k/summationdisplay
j=0yij−1=yi+y(V\S)−1,
where i∈S⊂V.Therefore
x(E(S)) = x(E)−x(δ(S, C 1, …, C k))
≤y(V)−1−yi−y(V\S)+1= y(S−i).
/square
4. F ORMULATIONS FOR THE DIRECTED PROBLEM
In order to achieve a tighter LP-relaxation, we transform the original problem
defined on an undirected graph into a problem defined on a directed graph, ob-
taining the at least version of the generalized minimum arborescence problem .
V1 V2 V3
V4 V5r
FIGURE 2. Example of a feasible solution of the L-GMST problem, in the case
when the underling graph is directed
The directed graph D=(Vd,A)is characterized by the vertex set Vd=V∪{r}
which consists of the vertices of the input graph Gand an artificial root vertex r
and by the arc set Awhich consists of opposite arcs (i,j)and(j, i)for each edge

At least version of the GMSTP 133
e=(i,j)∈Ehaving the same weight as the edge (i,j)∈E, plus a set of arcs
from the root node to each node from the vertex set V, having the cost equal to 0.
The directed version of the L-GMST problem is defined on the directed graph
D=(Vd,A)and consists of determining a minimum cost arborescence which
includes at least one node from every cluster.
In addition to the variables already introduced, we introduce the variables
wa∈{0,1},a∈Ato indicate whether an arc/primea/primeis contained in the spanning
arborescence.
We consider first a directed generalized cutset formulation of the L-GMST prob-
lem.
min/summationdisplay
e∈Ecexe
s.t. y (Vk)≥1, ∀k∈K={1, …, m }
w(A)=y(Vd)−1
w(δ−(S))≥yi, ∀i∈S⊆V, r /∈S (4.8)/summationdisplay
i∈Vxri=1 (4.9)
wij+wji=xe, ∀e=(i,j)∈E (4.10)
x, y, w ∈{0,1}. (4.11)
where for S⊆V, the set of arcs entering S , denoted by δ−(S), is defined as usually:
δ−(S)={(i,j)∈A|i/∈S, j∈S}.
In this model constraints (4.8) and (4.9) guarantee the existence of a path from the
artificial root node to any other selected node which includes only the selected
nodes.
LetPdcutdenote the projection of the feasible set of the linear programming
relaxation of this model into the (x, y)-space.
We introduced now a formulation of the L-GMST problem based on branch-
ings. Consider, as in the previous formulation, the digraph D=(Vd,A).W e
define the branching model of the L-GMST problem to be:
min/summationdisplay
e∈Ecexe
s.t. y (Vk)≥1, ∀k∈K={1, …, m }
w(A)=y(Vd)−1/summationdisplay
i∈Vxri=1
w(A(S))≤y(S−i),∀i∈S⊂V,2≤|S|≤n−1 (4.12)
w(δ−(Vk))≥1, ∀k∈K (4.13)
wij+wji=xe, ∀e=(i,j)∈E
x, y, w ∈{0,1}.
LetPbranch denote the projection of the feasible set of the linear programming
relaxation of this model into the (x, y)-space. Obviously, Pbranch ⊆Psub.

134 P. C. Pop, A. Horvat-Marc, Corina Pop Sitar
The following result holds:
Proposition 4.3. Pbranch =Pdcut∩Psub.
Proof. First we prove that Pdcut∩Psub⊆Pbranch .
Let(x, z)∈Pdcut∩Psub. Using the connectivity constrained (4.8) for S=Vk
and knowing that we have to span all the clusters implies that constrained (4.13)
is fulfilled. Therefore (x, z)∈Pbranch .
We show that Pbranch ⊆Pdcut∩Psub.
It is obvious that Pbranch ⊆Psub, therefore it remains to show Pbranch ⊆Pdcut.
Let(x, y)∈Pbranch .
Now we show that w(δ−(l))≤yl, forl∈Vk,k∈K.
TakeVl={i∈V|(i,l)∈δ−(l)}andSl=Vl∪{l}, then w(δ−(l)) =w(A(Sl))
and choose il∈Vl.
1≤/summationdisplay
l∈Vkw(δ−(l)) =/summationdisplay
l∈Vkw(A(Sl))≤/summationdisplay
l∈Vky(Sl\il)
=/summationdisplay
l∈Vkyl+/summationdisplay
l∈Vk/summationdisplay
j∈Vl\ilyj=1+/summationdisplay
l∈Vk/summationdisplay
j∈Vl\ilyj.
Therefore, for all lthere is only one il∈Vlwithyil/negationslash=0and
w(δ−(l)) =w(A(Sl))≤y(Sl\il)=yl.
For every i∈S⊂V
w(A(S)) =/summationdisplay
i∈Sw(δ−(i))−w(δ−(S))≤y(S−i),
which implies that:
w(δ−(S))≥/summationdisplay
i∈Sw(δ−(i))−y(S)+yi
=/summationdisplay
i∈S⎡
⎣1−/summationdisplay
l∈Vk\{i}w/parenleftbig
δ−(l)/parenrightbig⎤
⎦−y(S)+yi
≥/summationdisplay
i∈S⎡
⎣1−/summationdisplay
l∈Vk\{i}yl⎤
⎦−y(S)+yi=y(S)−y(S)+yi=yi.
/square
REFERENCES
[1] Dror, M., Haouari, M. and Chaouachi, J., Generalized Spanning Trees , European Journal of Opera-
tional Research, 120, 583-592, (2000)
[2] Feremans, C., Generalized Spanning Trees and Extensions , PhD thesis, Universite Libre de Bruxelles,
Belgium, (2001)
[3] Feremans, C., Labbe, M. and Laporte, G., A Comparative Analysis of Several Formulations of the
Generalized Minimum Spanning Tree Problem , Networks 39, Issue 1, 29-34, (2002)
[4] Myung, Y. S., Lee, C. H., Tcha, D. W. On the Generalized Minimum Spanning Tree Problem. Networks ,
26, 231-241 (1995)
[5] Pop, P. C., The Generalized Minimum Spanning Tree Problem , PhD thesis, University of Twente, The
Netherlands, (2002)

At least version of the GMSTP 135
[6] Pop, P. C., New Models of the Generalized Minimum Spanning Tree Problem , Journal of Mathematical
Modelling and Algorithms, 3, Issue 2, 153-166, (2004)
[7] Pop, P. C., On the Prize-Collecting Generalized Minimum Spanning Tree Problem , to appear in Annals
of Operations Research
[8] Pop, P. C., Kern, W. and Still, G., Approximation Theory in Combinatorial Optimization. Application
to the Generalized Minimum Spanning Tree Problem , Revue d’Analyse Numerique et de Theorie de
l’Approximation, Tome 34, No. 1, 93-102, (2005)
[9] Pop, P. C., Kern, W. and Still, G., A New Relaxation Method for the Generalized Minimum Spanning
Tree Problem , European Journal of Operational Research, 170, 900-908, (2006)
NORTH UNIVERSITY OF BAIAMARE,FACULTY OF SCIENCES
DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE
VICTORIEI 76, 430122 B AIAMARE,ROMANIA
E-mail address :pop
petrica@yahoo.com
E-mail address :hmandrei@yahoo.com
BABES¸-BOLYAI UNIVERSITY ,
FACULTY OF ECONOMICS ,
CLUJ-NAPOCA ,ROMANIA
E-mail address :sitarcorina@yahoo.com