Document [original]

FAKULT ¨

AT II

MATHEMATIK UND

NATURWISSENSCHAFTEN

Institut f ¨ur Mathematik

THE ZOO OF TREE SPANNER PROBLEMS

CHRISTIAN LIEBCHEN AND GREGOR W¨

UNSCH

No. 013/2006

The Zoo of Tree Spanner Problems∗

Christian Liebchen and Gregor W¨

unsch

July 10, 2007

Abstract

Tree spannerproblems haveimportant applications innetwork design, e.g. in the telecom-

munications industry. Mathematically, there have been considered quite a number of max-

stretch tree spanner problems and of average stretch tree spanner problems.

We propose a unified notation for 20 tree spanner problems, which we investigate for

graphs with general positive weights, with metric weights, and with unit weights. This

covers several prominent problems of combinatorial optimization. Having this notation at

hand, we can clearly identify which problems coincide. In the case of unweighted graphs,

the formally 20 problems collapse to only five different problems.

Moreover, our systematic notation for tree spanner problems enables us to identify a tree

spanner problem whose complexity status has not been solved so far. We are able to provide

an NP-hardness proof. Furthermore, due to our new notation of tree spanner problems,

we are able to detect that an inapproximability result that is due to Galbiati (2001, 2003)

in fact applies to the classical max-stretch tree spanner problem. We conclude that the

inapproximability factor for this problem thus is 2−ε, instead of only 1+√5

2≈1.618

according to Peleg and Reshef (1999).

1 Introduction

We consider a weighted connected undirected graph (G, w), where G= (V, E). We assume

the edge weights to be positive integers, occasionally after scaling. Let Tbe a spanning tree

of G. Depending on the context, we think of Teither as a subset of the edges of G, or as a

subgraph of G. For a spanning subgraph Hof Gand u, v ∈Vwe denote by

dH(u, v)

the length of a shortest (u, v)-path in H.

In [5] the t-tree spanner problem has been introduced as follows: Decide whether there

exists a t-tree spanner, i.e. a spanning tree Tof Gsuch that

dT(u, v)

dG(u, v)≤t, ∀(u, v)∈V⊗V:= V×V\{(v, v)|v∈V}.(1)

The corresponding optimization problem of constructing a spanning tree that realizes the min-

imum value tamong all spanning trees is called the MINIMUM MAX-STRETCH SPANNING

TREE (MMST) problem ([10]). Applications of the MMST problem arise in the area of net-

work design, e.g. in the telecommunications industry. There, trees are of particular interest,

because they allow to “keep the routing protocols simple” ([16]).

∗Supported by the DFG Research Center MATHEON in Berlin and by the DFG Research Training Group GK-621

“Stochastic Modelling and Quantitative Analysis of Complex Systems in Engineering” (MAGSI).

In [24] the related problem of finding a MINIMUM AVERAGE-STRETCH SPANNING TREE

(MAST) has been considered: Let w=1, i.e. Gis an unweighted graph, find a spanning tree T

that minimizes

{u,v}∈E\T

dT(u, v)

dG(u, v).(2)

Since for unweighted graphs there holds dG(u, v) = 1 for all {u, v} ∈ E, it is a simple obser-

vation ([1]) that this MAST problem turns out to be nothing but a special case of the MINIMUM

STRICTLY FUNDAMENTAL CYCLE BASIS (MSFCB) problem as it has been considered for

instance in [8]: Find a spanning tree Tthat minimizes

e={u,v}∈E\T

dT(u, v) + w(e).(3)

The MAST finds increasing attention in preconditioning, in particular for solving symmetric

diagonally dominant linear systems ([9]).

There is another related problem for which one can detect an even larger variety in notation.

In the SHORTEST TOTAL PATH LENGTH SPANNING TREE (STPLST, [8, 25]) problem we seek

for a spanning tree that minimizes

(u,v)∈V⊗V

dT(u, v).(4)

The very same problem has also been referred to as the MINIMUM ROUTING COST SPAN-

NING TREE (MRCST) problem ([26, 14]). In the special case of an unweighted graph, John-

son et al. ([20]) call it the SIMPLE NETWORK DESIGN problem. Alternatively, when con-

sidering complete graphs, Hu ([19]) introduced it as the OPTIMUM DISTANCE SPANNING

TREE problem. In [7], the MINIMUM AVERAGE DISTANCE (MAD) spanning tree problem

is considered—but setting the vertex weights in that model to one, this is another variant of

the STPLST problem.

Notice that also additive tree spanner problems attracted quite a number of researchers

(e.g. [22]). However, to keep the presentation focused we restrict ourselves to max-stretch

and average stretch tree spanners.

Outline. We propose a unified notation for the large variety of tree spanner problems in Sec-

tion 2. Subject to this notation we identify which problems coincide. More specifically, we

consider two problems Pand Qto coincide, if every spanning tree TPthat is optimum for P

constitutes an optimum solution for Q, and vice-versa. We use the notation P∼Qas a short-

hand. Notice that we have to choose this very discriminative equivalence relation. Otherwise,

if we allowed for general polynomial transformations, one could no more distinguish between

any two NP-complete problems. We provide coincidences for both maximum stretch tree span-

ners (Section 3.1) and average stretch tree spanners (Section 4.1), for the cases of graphs with

general weights, with metric weights, and with unit weights. We complement our analysis by

providing example graphs showing that there are no further coincidences. All the examples

consist of fairly small simple 2-vertex connected planar graphs.

Consider the very rich world of (in-) approximability results for tree spanner problems,

occasionally for special classes of graphs. We expect that having at hand a clear map of the

relationships between the various tree spanner problems, a certain cross-fertilization between

the different perspectives on much similar structures will occur. In Section 6.2 we make the first

step into this direction. In the context of tree spanners, as recently as 2004 the best known in-

approximability factor of the MMST problem has been cited as 1+√5

2([10]), being due to [23].

In this paper we observe that in the case of unweighted graphs the MMST problem coincides

with the MIN-MAX STRICTLY FUNDAMENTAL CYCLE BASIS (MMSFCB) problem, as it has

been stated in [12, 13]. There, an inapproximability factor of 2−εhas been achieved already

in 2001 ([12]). Hence, this applies immediately to the MMST problem as well. Moreover, in

the family of tree spanner problems we identify the only problem whose complexity status has

not been identified before. We provide an NP-hardness result for it.

2 A Unified Notation for Tree Spanners (UNTS)

There are three major criteria in which tree spanner problems may differ: First, either the maxi-

mum stretch or the average stretch is to be determined. Second, this objective may be computed

with respect to different sets of pairs of vertices, e.g. for (u, v)∈V⊗Vor only for {u, v} ∈ E\

T. Third, there have been considered various terms for the objective, e.g. dT(u,v)

dG(u,v)or dT(u, v) +

w(e).

In the remainder, we refer to a tree spanner problem Pthrough a triple

(goal,domain,term).

We consider the following family of tree spanner problems:

•goal

The goal is either the maximum stretch or the average stretch.

•domain

The domain is either {u, v} ∈ E\T,{u, v} ∈ E, or (u, v)∈V⊗V.

•term

The term may be one of dT(u, v) + w(e),dT(u, v),dT(u,v)

w(e), or dT(u,v)

dG(u,v).

Notice first that we do not consider (∗, V ⊗V, dT(u, v) + w(e)) and ∗, V ⊗V, dT(u,v)

w(e),

because w(e)is not properly defined for (u, v)∈V⊗V\E. Second, it could appear somehow

strange to count the weightof tree edges twice in the two tree spanner problems (∗, E, dT(u, v)+

w(e)). However, this is consistent with the UNTS. Moreover, this does not cause any degen-

eracies, because in the next two sections we exhibit that there is always some other tree span-

ner problem, which coincides with (∗, E, dT(u, v) + w(e)). Third, observe that for a given

graph, |E|and |V⊗V|are constant, and |E\T|is independent of the tree T. Hence, we prefer

to represent the goal “average” with the Psymbol.

We provide a first idea of the wide range of these tree spanner problems by locating several

well-known problems of combinatorial optimization within the UNTS:

•max, V ⊗V, dT(u,v)

dG(u,v)is the MMST problem ([5]),

•(max, V ⊗V, dT(u, v)) is the MINIMUM DIAMETER SPANNING TREE (MDST) prob-

lem ([16]),

•(P, V ⊗V, dT(u, v)) is the STPLST problem (or MRCST problem, [20]), and

•(P, E \T, dT(u, v) + w(e)) is the MSFCB problem ([8]).

We will establish that among the remaining 16 problems there is only one single problem which

does not coincide with one of these four prominent problems in the case of unweighted graphs.

Since its complexity status has not been identified before, we provide an NP-hardness proof

for it. However, in the case of weighted graphs there is a much larger variety of problems, in

particular in the context of average stretch tree spanners. For instance, in [9] the same tech-

niques are applied to both P, E, dT(u,v)

w(e)and P, E, dT(u,v)

dG(u,v). Nevertheless, in general

these problems do not coincide.

In Figure 1 we summarize all the coincidences that exist between tree spanner problems,

and which we are going to develop in the remainder of this paper.

Namely, in Sect. 3 we deal with max-stretch problems whereas in Section 4 average-stretch

problems are considered. We organize the sections by subdividing them into three parts where

we distinguish general, metric, and unit weights. However, we show that there is a bridge

between unweighted and integer-weighted tree spanner problems. Here, we aim at identifying

a weighted instance (G, w)immediately with the unweighted instance G′that results from

replacing every edge e={u, v}with weight w(e)with a uv-path P′

ehaving w(e)edges.

Observe that every spanning tree of G′has to contain at least w(e)−1edges of P′

e. Now,

consider the term dT(u, v)+w(e). Let Tbe some spanning tree of G. We construct a spanning

tree T′of G′such that if e∈Tthen P′

e⊆T′. This yields

dT(u, v) + w(e) = dT′(u′, v′) + 1,∀e={u, v} ∈ E\T, {u′, v′}=P′

e\T′.(5)

Hence, for the domain E\Tin conjunction with the term dT(u, v)+w(e)an optimum solution

to a weighted tree spanner problem isobtained bya kindof projection from an optimum solution

to the corresponding unweighted problem, and vice-versa.

Proposition 1. Let goal be a fixed optimization goal. Then, the weighted version and the

unweighted version of (goal, E \T, dT(u, v) + w(e)) coincide.

3 MAXIMUM STRETCH PROBLEMS

We start our tour through the zoo of tree spanner problems with maximum stretch tree spanner

problems. We first collect the pairs of problems which coincide, where we distinguish between

general weights, metric weights, and unit weights. Then, we examine example graphs showing

that there are no further coincidences.

3.1 Coincidences

It is an elementary observation that if two tree spanner problems coincide even for general

weights, in particular they also coincide for metric weights. Moreover, if two problems coincide

for metric weights, they immediately coincide for unweighted graphs, too. Hence, to present

the coincidences between maximum stretch tree spanner problems, we proceed from the most

general weight functions to the most specialized weight function.

General Weights. In the case of general weights, there are five families of coincident maximum

stretch tree spanner problems.

Proposition 2. The following twomaximumstretchproblemscoincide: (max, E\T, dT(u, v)+

w(e)) and (max, E, dT(u, v) + w(e)).

Proof. Assume for contradiction there was a weighted graph (G, w)such that a spanning tree T

that is optimum with respect to (max, E, dT(u, v)+w(e)) attains its maximum exclusively on

a tree edge e∈T. Then,

∀f={u, v} ∈ E\T:dT(u, v) + w(f)<2w(e).(6)

00000000

11111111

00000000

11111111

00000000

11111111

00000000

11111111

00000000

11111111

00000000

11111111

00000000

11111111

00000000

11111111

00000000

11111111

00000000

11111111

00000000

11111111

00000000

11111111

Maximum Stretch Tree Spanner

Average Stretch Tree Spanner

MMST MDST

STPLST

MSFCB

dT(u,v)+w(e)

dT(u,v)+w(e)dT(u,v)

dT(u,v)

w(e)

dT(u,v)

w(e)

dT(u,v)

w(e)

dT(u,v)

dG(u,v)

dT(u,v)

dG(u,v)

dT(u,v)

dG(u,v)

E\T

V⊗V

unweighted

weighted

metric

max

Figure 1: A guide to the zoo of tree spanner problems

Consider any edge f∈E\Twhose fundamental circuit Ccontains the edge e. Such an edge

exists because Gis 2-vertex connected. The total weight of the circuit Cis precisely w(C) =

dT(u, v) + w(f), and the weight of C\{e}is dT(u, v) + w(f)−w(e). By (6) there holds

dT(u, v) + w(f)−w(e)< w(e).(7)

Now, consider the spanning tree T′=T∪ {f} \ {e}. Any fundamental circuit (different

from C) with respect to Tthat contained the edge eis replaced with a subpath of C\ {e}.

As we only consider positive edge weights, by (7) the new fundamental circuit is strictly

shorter than the initial one. Hence, the spanning tree Thas not been optimum with respect

to (max, E, dT(u, v) + w(e)).

Proposition 3. The two problems (max, E \T, dT(u, v)) and (max, E, dT(u, v)) coincide.

Proof. Let Tbe an arbitrary spanning tree of (G, w). These two problems could only differ,

if the maximum in (max, E, dT(u, v)) is attained exclusively by a tree-edge e={u, v} ∈ T.

But in this case, dT(u, v) = w(e). As we only consider 2-vertex connected graphs, there exists

a circuit Cthrough e. The tree Tcannot contain all the edges of C. Hence, as we assume

the weight function wto be positive, there exists a non-tree edge e′={u′, v′} ∈ C\Tsuch

that dT(u, v)≤dT(u′, v′).

In the sequel we establish that the following five—recall that max, V ⊗V, dT(u,v)

w(e)is not

properly defined—tree spanner problems coincide: max,∗,dT(u,v)

w(e)and max,∗,dT(u,v)

dG(u,v).

In fact, most of the work has been done by Cai and Corneil ([5]):

Theorem 4 ([5]).Consider the following five tree spanner problems: max,∗,dT(u,v)

w(e)and

max,∗,dT(u,v)

dG(u,v). If for a given weighted graph (G, w)all of them attain an optimum stretch

value of t≥1, then these five problems coincide on (G, w).

However, subject to our definition of coincidence, we are even able to relax the assertion

of tbeing greater or equal than one. To that end, we start with an easy observation.

Lemma 5. Consider one of the four problems max, E, dT(u,v)

w(e)and max,∗,dT(u,v)

dG(u,v)for

some weighted graph (G, w). For the optimum stretch factor tthat can be obtained with respect

to this problem, there holds t≥1.

Proof. In the definition of the term dT(u,v)

dG(u,v),dG(u, v)is the length of a shortest uv-path in G.

Thus dT(u,v)

dG(u,v)≥1for all (u, v)∈V⊗V. When considering the term dT(u,v)

w(e)over the

domain E, for every tree edge e∈Tthis edge constitutes the unique uv-path in T. In

particular, dT(u,v)

w(e)= 1 for all e={u, v} ∈ T⊂E.

Proposition 6. If a weighted graph (G, w)admits a tree spanner Tsuch that t < 1subject

to max, E \T, dT(u,v)

w(e), then Tis unique optimum for all five problems max,∗,dT(u,v)

w(e)

and max,∗,dT(u,v)

dG(u,v).

Proof. So, let (G, w)be a weighted graph that admits a tree spanner Tsuch that t < 1subject

to max, E \T, dT(u,v)

w(e). Then, in order to prove the proposition it suffices to show that

1. for the four problems max, E, dT(u,v)

w(e)and max,∗,dT(u,v)

dG(u,v)there holds t= 1;

further,

2. for every spanningtree T′6=TofGthe five problems max,∗,dT(u,v)

w(e)andmax,∗,dT(u,v)

dG(u,v)

have stretch factor t′>1.

First, we prove 1. Therefore notice that for each e={u, v} ∈ Tit holds dT(u, v) = w(e).

Hence, for max, E, dT(u,v)

w(e)one immediately observes t= 1. Now, consider the prob-

lem max, V ⊗V, dT(u,v)

dG(u,v). Let uand vbe two vertices of Gand let Puv be the unique uv-

path in T. Assume for contradiction that Puv is not a shortest uv-path. So, let P′be a short-

est uv-path in G. Then, P′contains at least one edge f={u′, v′}that is not contained in T,

since otherwise Puv and P′contain a cycle in T. However, because of the proposition’s as-

sumption we know that dT(u′, v′)< w(f). Let ˜

Pbe the u′v′-path in T. Then this path ˜

Pcan

be used to construct an uv-path with length strictly smaller than the length of P′. From this con-

tradiction we conclude that for an arbitrary pair of vertices uand vthe uv-path in Tis a short-

est uv-path. Hence, dT(u, v) = dG(u, v)and the claim follows for max, V ⊗V, dT(u,v)

dG(u,v)

and hereby for max,∗,dT(u,v)

dG(u,v)with the two remaining domains as well.

Now, we prove 2. Therefore, let Tand T′be defined as in 2. From T′6=Twe con-

clude that there exists some edge e={u, v} ∈ T′\T. In particular, t < 1provides us

with Pf∈Puv w(f)< w(e), where Puv ⊆Tis the unique uv-path in T.

Consider the fundamental circuit CT(e) = {e}∪Puv that the edge einduces with respect

to T. As T′is a tree, the set of edges F=CT(e)\T′is nonempty, and in particular e6∈ F,

because e∈T′.

Because of w(e)> w(f)for all edges f∈Puv and since we are only considering positive

weight functions w, it remains to detect some edge f∈F, such that e∈CT′(f). Since the

fundamental circuits with respect to T′form a basis of the cycle space C(G), and CT(e)∈

C(G), there exists a set F′⊆E\T′such that

CT(e) = X

f∈F′

CT′(f),

where we consider the symmetric difference. Due to the special structure of cycle bases that

are associated with spanning trees, we know that F′⊂CT(e)\T′, in fact F′=F([2]). In

particular, as by definition the edge eis contained in CT(e),ehas to appear in at least one

fundamental circuit CT′(f)that is induced by an edge f={u′, v′} ∈ F.

Corollary 7. The following five problems coincide: max,∗,dT(u,v)

w(e)and max,∗,dT(u,v)

dG(u,v).

Proof. Consider an optimum solution Twith respect to max, E \T, dT(u,v)

w(e). In the case

of a stretch factor t≥1we are done immediately by applying Theorem 4. Otherwise, i.e.,

if t < 1, Proposition 6 ensures optimality and uniqueness of Tsubject to all five optimization

problems that we consider here.

In particular, all the maximum stretch tree spanner problems that involve fractions coincide.

Metric Weights. For maximum stretch tree spanner problems, there are no coincidences in the

case of metric weights, which do not apply already to the general case.

Unit Weights. For an arbitrary tree Tof an unweighted connected graph G(or having weights

w=1) with nvertices and medges, there holds

max

e={u,v}∈E{dT(u, v) + w(e)}= max

e={u,v}∈E\T{dT(u, v) + w(e),2}(8)

= max

e={u,v}∈E{dT(u, v) + 1}(9)

= max

e={u,v}∈E\T{dT(u, v) + 1,2}.(10)

Moreover, by w(e) = 1 we obtain immediately dT(u, v) = dT(u,v)

w(e). Finally, in the case of

an unweighted graph, for every edge e={u, v}there holds dT(u, v) = dT(u,v)

dG(u,v). Together

with (8)–(10) and Corollary 7 we conclude

Proposition 8. Let Gbe an unweighted graph. Except for (max, V ⊗V, dT(u, v)), all max-

stretch tree spanner problems coincide.

3.2 Anticoincidences

In order to prove for two problems that they do not coincide, we profit from the following tran-

sitive relation: If the problems do not coincide for unweighted graphs, then they do not coincide

for graphs with metric weights. Furthermore, if there is a graph with metric weights for which

the sets of optimum solutions for two tree spanner problems have empty intersection, then these

problems cannot coincide for general weights either. Thus, we provide the relevant anticoinci-

dences by moving from the most specialized weight function to general weight functions.

Unit Weights. As by Proposition 8 there are only two different maximum stretch tree spanner

problems in the case of unweighted graphs, we only have to establish one single anticoinci-

dence.

Example 9 (MMST vs. MDST).Consider the unweighted simple graph Gin Figure 2(a).

Recall from Proposition 8 and from Theorem 4 that in the unweighted case we may think of the

MMST problem as (max, E \T, dT(u, v)). Hence, we are looking for a spanning tree whose

non-tree edges are linked by paths in Twhose maximum length is minimal. The spanning tree

that we highlight in Figure 2(b) attains an objective value of two. Moreover, every spanning

tree that attains an objective value of two has to induce all five triangles of Gas its fundamental

circuits. Thus, such a spanning tree must contain the four edges that are not incident with the

infinite face. So it must not contain the edge e.

(a)

(b)

(c)

Figure 2: An unweighted graph and example trees which show that MMST and MDST do not

coincide

In contrast, for that in the MDST problem a diameter of three can be achieved, the leftmost

vertex and the rightmost vertex have to be connected via a path of three edges. Observe that

there is only one such path. But this includes the edge e, see Figure 2(c) for one of the two

optimum trees.

Metric Weights. In order to complement the results of Section 3.1, we have to show that the

following three problems do not coincide:

•(max, E \T, dT(u, v) + w(e)),

•(max, E \T, dT(u, v)), and

•max, E \T, dT(u,v)

w(e).

Fortunately, there exists a fairly small graph with metric weights such that the unique optimal

solutions for these three problems are disjoint.

Example 10 ((max, E \T, dT(u, v) + w(e)) vs. (max, E \T, dT(u, v))

vs. max, E \T, dT(u,v)

w(e)).Consider the graph in Figure 3(a). In Table 1 the objective values

of the three spanning trees in Figures 3(b)–3(d) with respect to the three objective functions are

collected.

333

(a)

333

(b)

333

(c)

333

(d)

Figure 3: A graph with metric weights and its different optima with respect to the objective

functions (max, E \T, goal), where goal ∈ {dT(u, v) + w(e), dT(u, v),dT(u,v)

w(e)}

Table 1: The values with respect to the different objective functions for the spanning trees in

Figures 3(b) to 3(d)

Tree dT(u, v) + w(e)dT(u, v)dT(u,v)

w(e)

Figure 3(b) 10 77

Figure 3(c) 11 66

Figure 3(d) 12 7 3

There are precisely seven circuits in G. One can easily check that the values 10 and 6are the

best values with respect to the objective functions dT(u, v) + w(e)and dT(u, v), respectively,

even when considering arbitrary sets of three circuits. Finally, performing a simple inspection

of the few relevant cases one can further check that no other spanning tree achieves better values

with respect to the three objective functions.

General Weights. As there are no coincidences between maximum stretch tree spanner prob-

lems which do only apply to metric weights but not to general weights, this paragraph has to

remain void.

4 AVERAGE STRETCH PROBLEMS

Our tour through the average stretch tree spanner problems follows the trace of our expedition

through the maximum stretch tree spanner problems. But we will find many more different

problems in the average stretch case.

4.1 Coincidences

Comparing the maximum stretch case to the average stretch case on general weights, metric

weights, or unit weights, the number of different problems is by up to four larger for average

stretch tree spanners.

General Weights. There are only two pairs of average stretch tree spanner problems that coin-

cide for general weights.

Proposition 11. It holds that the two average stretch problems (P, E, dT(u, v) + w(e)) and

(P, E, dT(u, v)) coincide.

Proof. For every spanning tree T, the objective values of these two problems differ precisely

by Pe∈Ew(e), being independent of T.

Proposition 12. The twoaveragestretchproblemsP, E \T, dT(u,v)

w(e)andP, E, dT(u,v)

w(e)

coincide.

Proof. For every spanning tree T, the objective values of these two problems differ precisely

by Pe∈T

dT(u,v)

w(e). As for every edge e={u, v} ∈ Tthe unique path in Tbetween its endpoints

is just the edge e, there holds dT(u, v) = w(e). Thus, Pe∈T

dT(u,v)

w(e)=n−1, which again is

independent of T.

Metric Weights. Much similar to the case of maximum stretch tree spanners, for metric weight

functions four problems whose objective functions involve fractions coincide.

Proposition 13. Let (G, w)be an undirected graph with a metric weight function won the

edges. Let domain be either E\Tor E, and let term be one of dT(u,v)

w(e)and dT(u,v)

dG(u,v). Then,

the four problems (P,domain,term)coincide.

Proof. In the case of a metric weight function won the edges, for every edge e={u, v} ∈ E

there holds dG(u, v) = w(e). Hence, for each of the two domains that we consider here, the

two problems (P,domain,∗)coincide.

Moreover, for every tree edge e={u, v} ∈ Tthere holds dT(u,v)

w(e)= 1. Thus, for every

spanning tree its objective value with respect to the domain Eis precisely n−1greater than

the objective value with respect to the domain E\T.

Unit Weights. With the exception of the average stretch tree spanner problems that are defined

for V⊗V, all other average stretch tree spanner problems coincide on unweighted graphs.

Similarly to (8)–(10) we find,

e={u,v}∈E

dT(u, v) + w(e) = 

X

e={u,v}∈E\T

dT(u, v) + w(e)

+ 2(n−1) (11)

=

X

e={u,v}∈E

dT(u, v)

+m(12)

=

X

e={u,v}∈E\T

dT(u, v)

+m+n−1.(13)

Again, we profit from the fact that for every edge e={u, v}there holds dT(u, v) = dT(u,v)

w(e)=

dT(u,v)

dG(u,v). Together with (11)–(13) we conclude

Proposition 14. Let Gbe an unweighted graph. Then the following eight unweighted tree

spanner problems coincide: (P, E \T, ∗)and (P, E, ∗).

4.2 Anticoincidences

In the case of average stretch tree spanner problems, it will turn out that even for the unweighted

case, both problems with domain V⊗Vdo not coincide with any other problem.

Unit Weights. In the case of the most special weights, the following Example 15 shows that we

remain with 3problems.

Example 15 (MSFCB vs. STPLST vs. P, V ⊗V, dT(u,v)

dG(u,v)).Consider the unweighted pla-

nar graph Gin Figure 4. Observe that the graph from Figure 2 can be obtained from Gsimply

by contracting one single edge. Again, the unique minimum cycle basis of Gconsists of the

five circuits which are the boundary of the finite faces of G. Hence, the optimum solution value

of the MSFCB problem on Gis 16 and it can be obtained by the fundamental circuits that are

induced by eight spanning trees, one of which we display in Figure 4(b). These eight spanning

trees all contain the four edges of Gwhich are not incident with the infinite face of G, and yield

objective values of at least 66 and 230

6for the STPLST problem and for P, V ⊗V, dT(u,v)

dG(u,v),

respectively.

(a) (b) (c) (d)

Figure 4: An unweighted graph and example trees which show that none of MSFCB, STPLST,

and P, V ⊗V, dT(u,v)

dG(u,v)coincide

In contrast, the spanning tree in Figure 4(c) is one of the four optimum solutions for the

STPLST problem. Their objective value is 62. On the contrary, for the MSFCB problem and

for P, V ⊗V, dT(u,v)

dG(u,v)they only achieve objective values of 18 and 228

6, respectively.

Finally, the four spanning trees which are optimum with respect to P, V ⊗V, dT(u,v)

dG(u,v),

see Figure 4(d) for an example, achieve an objective function value of 227

6. But for the objective

functions of MSFCB and STPLST these trees are suboptimal because of objective values of

only 17 and 63, respectively.

Metric Weights. To discover more anticoincidences we take a look at graphs with a metric

weight function.

Example 16 (MSFCB vs. (P, E, dT(u, v)) vs. (P, E \T, dT(u, v))).We investigate the

graphGwith a metric weight function wthat isdisplayed in Figure 5(a). There are precisely two

circuits in (G, w)which have weight 18, and another two circuits which have weight 19. There

are indeed four spanning trees which achieve an objective function value of 18 + 18 + 19 = 55

with respect to MSFCB (see e.g. Figure 5(b)). But since all of them include two edges of

weight seven, they only achieve objective values of 62 and 40 with respect to (P, E, dT(u, v))

and (P, E \T, dT(u, v)), respectively.

(a)

(b)

(c)

(d)

Figure 5: A graph with metric weights and example trees which show that none of MSFCB,

(P, E \T, dT(u, v)), and (P, E, dT(u, v)) coincide

Table 2: The objective values to the four considered problems for the trees of Figures 6(b)

and 6(c).

Tree (P, E \T, (P, E \T, (P, E \T, (P, E,

dT(u,v)

w(e))dT(u, v) + w(e)) dT(u, v)) dT(u, v))

Figure 6(b) 4 + 4

7≈4.57 46 32 55

Figure 6(c) 4 + 5

9≈4.55 51 35 56

In contrast to the optima with respect to MSFCB, there exist two spanning trees which only

contain one single edge of weight seven each, but admit the second smallest set of fundamental

circuits: 18 + 19 + 19 = 56. Hence, these are precisely the trees which admit an objective

function value of 38, being optimum with respect to (P, E \T, dT(u, v)). One of them is

depicted in Figure 5(c). Their objective value with respect to (P, E, dT(u, v)) is 57.

Since we identified all the optima with respect to MSFCB and (P, E \T, dT(u, v)), it

suffices to provide some spanning tree Tthat attains a smaller objective function value with

respect to (P, E, dT(u, v)) than the former trees did. Indeed, the spanning tree Tthat we

display in Figure 5(d) yields an objective function value of only 56. One can easily observe

that Tis the unique minimum spanning tree of (G, w). Actually, it is even the unique optimum

solution with respect to (P, E, dT(u, v)).

Example17(P, E \T, dT(u,v)

w(e)vs. {(P, E \T, dT(u, v) + w(e)),(P, E \T, dT(u, v))

,(P, E, dT(u, v))}).Consider the graph Gof Figure 6(a). Because of the very regularly struc-

tured weights we need only to consider two families of spanning trees: those that include the

edge of weight 9, and those which do not. Within both families then all trees constitute in-

distinguishable solutions for all the considered problems. Representatives for the families are

depicted in Figures 6(b) and 6(c), respectively. The following table now proves the desired

claim: whereas for the fractional problem, P, E \T, dT(u,v)

w(e)it does not pay off to include

the “expensive” edge of weight 9, it does for the other three problems. It rather turns out to

be good to include this particular edge such that it can be used as a shortcut when consider-

ing dT(u, v)for (u, v) = e∈E\T.

General Weights. At last we need to consider graphs with non-metric weight functions to prove

the remaining anticoincidences.

Example18(P, E \T, dT(u,v)

w(e)vs. {P, E \T, dT(u,v)

dG(u,v),P, E, dT(u,v)

dG(u,v)}).Consider

the graph with non-metric weights in Figure 7. A first observation is that the edge with weight 8

is not metric. More important, the edge with weight 1is included in every optimal tree for all

(a)

(b)

(c)

Figure 6: A graph with metric weights and example trees which show that none of MSFCB,

(P, E \T, dT(u, v)), and (P, E, dT(u, v)) coincide with P, E \T, dT(u,v)

w(e)

the three problems. Otherwise we immediately have a contribution of 14—which is the length

of a shortest circuit through this edge—whereas any other tree induces shorter circuits w.r.t.

both dT(u,v)

dG(u,v)and dT(u,v)

w(e)even when considering the sum over all edges.

So, we remain with 5different trees. Among these, due to symmetry reasons it suffices to

consider only three trees, cf. 7(b)-7(d).

The following table provides the values for the three trees with respect to the different

problems showing that the tree in 7(b) is the unique optimal solution to P, E \T, dT(u,v)

w(e)

whereas the tree indicated in Figure 7(c) is optimum forthe othertwo problems, P, E \T, dT(u,v)

dG(u,v)

and P, E, dT(u,v)

dG(u,v).

Table 3: The objective values of the spanning trees in Figure 7 w.r.t. the three problems of

Example 18. A term of 1

840 is factored out for clarity reasons.

Tree P, E \T, dT(u,v)

w(e) P, E \T, dT(u,v)

dG(u,v) P, E, dT(u,v)

dG(u,v)

Figure 7(b) 2555 2720 5240

Figure 7(c) 2583 2688 5208

Figure 7(d) 3612 3612 6252

(a)

(b)

(c)

(d)

Figure 7: A weighted graph and example trees. Figures (b) and (c) show

that P, E \T, dT(u,v)

w(e)does neither coincide with P, E \T, dT(u,v)

dG(u,v)nor with

P, E, dT(u,v)

dG(u,v).

Example 19 (P, E \T, dT(u,v)

dG(u,v)vs. P, E, dT(u,v)

dG(u,v)).We will show the anticoincidence

of the two tree-spanner problems with the help of the weighted graph (G, w)in Figure 8(a).

The dots in the figure shall indicate that we assume a sufficiently large number of clips, i.e.

4-circuits that share one common edge eor f, respectively. Let Mdenote this number. Further,

we will refer to the edges with weight equal to 101 as clip-edges.

Recall from Proposition 13 that the two problems coincide in the case of metric weights.

Hence, we chose the weight function wsuch that precisely one edge is not metric: the edge g.

To show the anticoincidence we will argue as follows: in the beginning we show that each

spanning tree Tthat is optimal for any of the two problems must have a certain structure. First,

all edges having weight one are included in T, second, Tdoes not contain any clip-edge, and

third, the edges eand fare in T. See Figure 8(b), where we highlight edges that have to be

in T. Edges that are not in Tare depicted by dotted lines in this figure.

Observe that as we obtain this structure for parts of the graph where all edges are metric,

the structural properties apply to the optimum solutions subject to both objective functions that

we are investigating in this example. Thereafter, having this common structure, optimal trees

to P, E \T, dT(u,v)

dG(u,v)and P, E, dT(u,v)

dG(u,v)become distinguishable on the remaining part

of the graph, where the only non-metric edge gis going to play a key role.

So, we start motivating the mentioned structure of an optimal tree T. We first show that

w(a) = 1 implies a∈T. Notice first that for any of the 2Mclips at least one edge of the clip

with weight one has to be in Tbecause otherwise the tree Twould not be connected. Hence,

assume that for a clip exactly one edge of weight one and its clip-edge are contained in T.

In that case, however, we get immediately a contradiction to the optimality of T: A simple

exchange of the clip-edge by the non-tree edge with weight one within this clip instantly effects

a better tree. To see this, observe that for no other pair of vertices in Gthe corresponding path

in Tcan traverse one of these two edges and compare the according values dT(x,y)

dG(x,y).

111

...

100100

100

100 100

101

(a)

...

(b)

Figure 8: A weighted graph on which the optimum solutions for P, E \T, dT(u,v)

dG(u,v)and

P, E, dT(u,v)

dG(u,v)do not coincide. Whereas for the first objective it pays off to include the

non-metric edge ginto an optimal tree an optimal solution to P, E, dT(u,v)

dG(u,v)is attained

without the edge g.

Now, we know w(a) = 1 ⇒a∈T. Next, we establish that w(a)>100 implies a6∈ T

in any tree that is optimal with respect to one of the two objectives that we are investigating in

this example. To this end, consider one bundle of clips, say the one that contains the edge e,

and assume an optimal tree Tcontains a clip-edge. Since we already know that the edges

having weight one are in T, the tree can contain at most one clip-edge, because otherwise the

tree Twould include a cycle. Similarly, we conclude that e6∈ T. Again, such a structure

contradicts the optimality of T, because another local change on Timproves the tree: This

time we exchange the clip-edge cthat we assume to be contained in Twith the edge eand

obtain a different tree T′=T∪{e}\{c}. This exchange shortens the length of the path in T

between the vertices incident to e, hereby shortening the distances of all paths within Tthat

contain these two vertices. In addition, even when comparing the value dT(x,y)

dG(x,y)of the non-tree

edge ew.r.t. Twith the corresponding value of the non-tree edge cw.r.t. T′an improvement is

obtained. Notice that here we only define the particular tree T′to contain the edge e. But so far

nothing is said whether eis contained in any optimum tree.

The last structural property, that we are about to develop for an optimal tree Twith respect to

any of the two objective functions, is {e, f} ⊂ T. We already know that Tcontains all edges of

weight one and no clip-edge. Hence, at least one of the edges eand fis in T, because otherwise

the tree Twas disconnected. So we assume for contradiction without loss of generality that e∈

Tbut f /∈T. Then, consider the unique path Pbetween the vertices uand vin Twhere

obviously f6∈ Timplies e6∈ P. Now, an exchange of any of the edges of Pby the edge fwill

lead to a contradictionto the choice of T, which was an optimal tree. One cansee this as follows:

before the exchange, each f-clip-edge induces a path in Tof length dTat least 126. Therefore,

in both objectives each f-clip-edges contributes at least M·126

101 . After the exchange—i.e. now

with f∈T—this amount decreases to M·102

101 . It is clear that we may choose the parameter M

so large that this gain compensates the possibly appearing increases of contributions of the

remaining part of the graph that is independent of M.

This way we force {e, f} ⊂ T, and in a sense decouple the clip-edges from the remainder

of the tree.

At this point we developed all of the structural properties of an optimal tree T. Let us

emphasize that the properties hold for optima of both objectives, because up to this point we

only argued for parts of the graph on which the two objective values differ by a constant term,

because the edges within the clips are all metric.

For the remainder of the graph we discuss the effect of adding two more edges to our tree T.

Observe that there are exactly two spanning trees that contain the edge gand three which do

not.We start by computing the objective value Kthat the three non-tree edges that are distinct

from clip-edges contribute. If g∈T, then K=491

33 ∈[14.87,14.88]. Otherwise, if g6∈ T,

there are two trees for which K=6727

450 ∈[14.94,14.95], and one for which K > 16. Hence,

for the domain E\T, the two trees that contain the expensive non-metric edge gturn out to be

optimal. In contrast, for the domain Eit does not pay off to include the non-metric edge ginto

the tree: it costs 10

9instead of only one for any other tree edge, which is in particular metric,

and this extra cost of more than 0.1gets not compensated by a reduction of less than 0.08 in K.

Hence, on (G, w)the average stretch tree spanner problem P, E, dT(u,v)

dG(u,v)is optimized by

two of the three trees with g6∈ T.

5 MAX-STRETCH And AVERAGE-STRETCH ProblemsNever

Coincide

In this section we aim at detecting anticoincidences between max-stretch and average-stretch

problems. Therefore we consider unweighted versions of the problems.

Example 20 (MMST vs. MSFCB).Consider the unweighted simple 2-vertex connected undi-

rected planar graph Gin Figure 9. We will argue that an optimum solution for the MSFCB

problem contains the edge e, whereas an optimum solution for the MMST does not.

(a)

(b)

(c)

Figure 9: An unweighted graph with representatives of optimal solutions to MMST and MSFCB

Consider the MMST problem. We construct a spanning tree Tall of whose fundamental

circuits have at most four edges, cf. Figure 9(b). First, observe that there has to hold f∈T,

because the only 4-circuits through the south-east most and through the south-west most vertices

share the edge f. But then, in order to prevent a 5-circuit, the two edges that are incident with f

must be contained in T, too. In turn, e6∈ T. The five fundamental circuits of such a spanning

tree Tthus have lengths (3,4,4,4,4).

In contrast, every optimum spanning tree for the MSFCB problem induces fundamental

circuits of lengths (3,3,3,4,5), see Figure 9(c) for an example. But this can only be achieved

by including the edge ein the spanning tree, because the only three triangles in Gall share this

edge.

Example 21 (MDST vs. {STPLST,(P, V ⊗V, dT(u,v)

dG(u,v))}).Consider the unweighted undi-

rected graph Gin Figure 10. We will argue that the set of spanning trees which are optimum for

MDST is disjoint from the set of spanning trees optimal for STPLST or P, V ⊗V, dT(u,v)

dG(u,v).

(a)

(b)

(c)

Figure 10: An unweighted graph and parts of example trees which show that MDST does

neither coincide with STPLST nor with P, V ⊗V, dT(u,v)

dG(u,v)

We start by detecting a necessary condition for a spanning tree to be optimum for MDST.

To that end, first observe that an optimum spanning tree Twith respect to MDST achieves

a diameter of four. Consider the vertex u. The unique shortest circuit Cthrough uhas five

edges, whereas the second-shortest circuit through uhas six edges. Hence, in a minimum

diameter spanning tree Tin G, the circuit Cis the only fundamental circuit with respect to T

that contains the vertex u. But since G\{u}is 2-vertex connected, this implies the three bold

edges in Figure 10(b) to be contained in T, in particular e∈T.

In contrast, one can check that each of the twelve spanning trees which are optimum for

STPLST (having objective value 86) is also optimum for P, V ⊗V, dT(u,v)

dG(u,v)(having objec-

tive value 54), and vice-versa. Moreover, in each of these trees there holds δ({v})⊂T, where

δ({v})is the cut induced by v. In particular, e6∈ T.

Finally, the next example covers the remaining anticoincidences.

Example 22 ({MMST, MSFCB}vs. {MDST, STPLST,P, V ⊗V, dT(u,v)

dG(u,v)}).A key dif-

ference between MMST and MSFCB ontheone side, and MDST, STPLST, and P, V ⊗V, dT(u,v)

dG(u,v)

on the other side, is that the former problems may be regarded as to have only the set of non-tree

edges E\Tas domain, whereas the latter have V⊗Vas domain. But only the latter ensures

a kind of global perspective for every spanning tree. With E\Tas domain, an accordion-

like tree as the one that we already displayed in Figure 2(b) admits a much more local way of

counting.

Consider again the unweighted graph in Figure 2. By the very same arguments which

showed that e∈Tfor every spanning tree Twhich is optimum for MMST, this edge is also

contained in every spanning tree which is optimum for MSFCB. More precisely, the four span-

ning trees which are optimum for MMST are precisely the optimum solutions for MSFCB—

these four spanning trees only differ in how the left- and the rightmost vertex is connected to

the tree.

Similarly, the two spanning trees of minimum diameter are precisely the optimum solutions

for STPLST (having objective value 42) and even for P, V ⊗V, dT(u,v)

dG(u,v)(having objective

value 28). These two trees only differ in which endpoint of the edge ebecomes the vertex of

degree four in T.

To summarize this section, there is not one single bridge between MAX-STRETCH and AVE-

RAGE STRETCH tree spanner problems. In contrast, there exists a related pair of problems for

which such a bridge between the maximum objective and the sum objective was established. In

[6] it has been shown that any solution to the general MINIMUM CYCLE BASIS (MCB) problem

is also a solution to the problem of computing a cycle basis whose longest circuit is minimum.

Here, it is well-known that the MCB problem can be solved in polynomial time ([18]), more

precisely in O(m2n+mn2log n)([21]).

6 First Benefit of the UNTS

Recall that whenever a spanner problem (goal,domain,term)is NP-hard in the unweighted

case, it is in particular NP-hard in its weighted versions, too. We are aware ofthree suchnegative

complexity results for unweighted tree spanner problems.

Theorem 23 ([20]).The STPLST problem is NP-hard.

Theorem 24 ([8]).The MSFCB problem is NP-hard.

Theorem 25 ([5]).The MMST problem is NP-hard.

There have even been identified special classes of graphs on which these problems are

still NP-hard. For instance, think of the MMST problem on planar graphs ([11]), on chordal

graphs ([3]), and on chordal bipartite graphs ([4]).

But there is also one positive complexity result that has been obtained for a tree spanner

problem.

Theorem 26 ([17]).The weighted MDST problem can be solved in O(mn +n2log n)time.

Now, the UNTS provides us with a clear perspective on 20 tree spanner problems. In par-

ticular, Examples 15, 22, and 21 establish that none of the above complexity results apply to

the problem P, V ⊗V, dT(u,v)

dG(u,v). Fortunately, we are able to settle its complexity status in

Section 6.1 by establishing NP-hardness.

Moreover, by Proposition 8 we know that in the case of unweighted graphs the classical

maximum stretch tree spanner problem max, V ⊗V, dT(u,v)

dG(u,v)coincides with (max, E \T, dT(u, v) + w(e)).

In Section 6.2 we compare two inapproximability results that have been obtained for these prob-

lems. Interestingly enough, the result which had never been stated before in the language of tree

spanners turns out to be stronger.

6.1 NP-hardness of P, V ⊗V, dT(u,v)

dG(u,v)

Theorem 27. The average stretch tree spanner problem P, V ⊗V, dT(u,v)

dG(u,v)is NP-hard.

Proof. As our proof is similar to the proof for Theorem 23 as it has been given by John-

son et al. ([20]), we adopt the notation of [20]. We consider the following problem, which

is known to be NP-hard (Problem SP2 in [15]):

EXACT COVER BY3-SETS (X3C): Given a family S= (σ1,...,σs)of 3-element

subsets of a set T= (τ1,...,τ3t). Does there exist a subfamily S′⊆Sof sets

with pairwise empty intersection, such that ˙

Sσ∈S′σ=T?

Given an instance Iof X3C, we define an unweighted simple undirected graph G= (V, E)as

follows, see Figure 11 for an example:

•R={ρ0, ρ1, . . . , ρr}, where r:= |T|2+ 2 ·|S|·|T|+ 1,R0={ρ0}, R∗=R\R0,

•V=R∪S∪T,

•E={{ρi, ρ0}:i= 1,...,r}∪{{ρ0, σ}:σ∈S}∪{{σ, τ}:τ∈σ∈S},

ρ1,...,ρr

ρ0

...

123456789

Figure 11: The instance of P, V ⊗V, dT(u,v)

dG(u,v)that we associate with the in-

stance {(1,2,3),(3,4,5),(4,5,7),(6,8,9),(7,8,9)}of X3C

Denote by Xthe number of pairs of elements of Tthat are not contained together in any of the

sets of S, i.e.

X:= |{(τ1, τ2)∈V⊗V:∀σ∈S:τ16∈ σor τ26∈ σ}|.(14)

We will prove that P, V ⊗V, dT(u,v)

dG(u,v)has a solution of value at most

|V|2−|V|+|T|2+ 6 ·|S|−5·|T|−X, (15)

if and only if the answer to the instance Iis YES.

We denote a spanning tree of Gthat contains the edge {ρ0, σ}for all σ∈Sastar tree.

Claim. Every optimum solution of P, V ⊗V, dT(u,v)

dG(u,v)is a star tree.

Claim. In Table 4, we investigate the distances between any pair of nodes in G, in an arbitrary

star tree F∗, and in an arbitrary non-star tree F.

In the case of a non-star tree F, there exists one vertex s′∈Ssuch that dF(ρi, s′)≥4

for all i= 1,...,r. In particular, dF(ρi,s′)

dG(ρi,s′)≥2, whereas dF⋆(ρi,s′)

dG(ρi,s′)= 1, cf. the (∗)-entry in

Table 4. Hence, when considering R∗⊗S, by the choice of rthe objective value of Fis by at

least |T|2+ 2 ·|S|·|T|+ 1 larger than the one of F∗.

Table 4: Distances between pairs (u, v)of nodes within the graph. The first column denotes the

cardinality of the considered subset of V⊗V.

set of uset of vnumber of node pairs dG(u, v)dF∗(u, v)dF(u, v)

R0R∗|T|2+ 2|S|·|T|+ 1 1 1 1

R0S|S|1 1 ≥1

R0T|T|2 2 ≥2

R∗R∗(|T|2+ 2|S|·|T|+ 1)·

(|T|2+ 2|S|·|T|) 2 2 2

R∗S(|T|2+ 2|S|·|T|+ 1) ·|S|2 2 (∗)

R∗T(|T|2+ 2|S|·|T|+ 1) ·|T|3 3 ≥3

S S |S|·(|S|−1) 2 2 ≥2

S T |S|·|T| {1,3} ≤ 3≥1

T T |T|·(|T|−1) −X2≤4≥2

T T X 4 4 ≥4

According to Table 4 this can only be compensated on S⊗Tand on T⊗T. But there,

for (u, v)∈S⊗Tthere holds

dF∗(u, v)

dG(u, v)≤dF(u, v)

dG(u, v)+ 2,

and for (u, v)∈T⊗Tthere holds

dF∗(u, v)

dG(u, v)≤dF(u, v)

dG(u, v)+ 1.

Hence, any non-star tree Fcan only gain |T|2+ 2 · |S| · |T|on S⊗Tand T⊗T, which is

strictly smaller than its loss on R∗⊗S.

Now that we know that an optimum solution to P, V ⊗V, dT(u,v)

dG(u,v)is always a star tree,

we will compute the objective value of an arbitrary star tree F∗. According to Table 4, it remains

to investigate in detail pairs of vertices from the sets S⊗Tand T⊗T. We first examine the

set S⊗Tand compute for an arbitrary star tree F∗

(u,v)∈S⊗T

dF∗(u, v)

dG(u, v)=X

(u,v)∈S⊗T

dF∗(u,v)=1

dF∗(u, v)

dG(u, v)+X

(u,v)∈S⊗T

dG(u,v)=3

dF∗(u, v)

dG(u, v)+

(u,v)∈S⊗T

dG(u,v)=1, dF∗(u,v)=3

dF∗(u, v)

dG(u, v)

=|T|+|S|·(|T|−3) + X

(u,v)∈S⊗T

dG(u,v)=1, dF∗(u,v)=3

dF∗(u, v)

dG(u, v)

=|T|+|S|·(|T|−3) + 3 ·(3|S|−|T|))

=|S|·|T|−2·|T|+ 6 ·|S|.

As this value is independent of F∗, we conclude that any two star trees differ in their objective

value only for pairs (u, v)∈T⊗T.

Recall the definition of Xin (14). Among the pairs (u, v)∈T⊗T, there are pre-

cisely Xfor which dG(u, v) = 4—and thus dF∗(u, v) = 4—and precisely |T|2− |T| − X

for which dG(u, v) = 2. As F∗is a star tree, we know that dF∗(u, v)∈ {2,4}for ev-

ery (u, v)∈T⊗T. Recall that the quantity Xonly depends on the instance Iof X3C.

Hence, a spanning tree F∗is optimum for P, V ⊗V, dT(u,v)

dG(u,v), if and only if it is a star tree

that maximizes the number Yof pairs (u, v)∈T⊗Tfor which dF∗(u, v) = 2. How large

can Yget?

We prefer to account for the quantity Yfrom an alternative perspective. To that end, con-

sider the edges F∗

ST := F∗∩(S×T). Note that |F∗

ST |=|T|, because F∗is a star tree. Now,

we define a function p(e)for the edges e= (σ, τ)∈F∗

ST ,

p(e) = 





2,if |δF∗(σ)|= 4,

1,if |δF∗(σ)|= 3,and

0,otherwise.

Hereby, Y=Pe∈F∗

ST p(e). Then the following statements are equivalent:

•Y= 2|T|.

•For all e∈F∗

ST ,p(e) = 2.

•For all σ∈S,|δF∗(σ)| ∈ {1,4}.

Finally, we provide a bijection between star trees F∗of Gwith |δF∗(σ)| ∈ {1,4}, for all σ∈S,

and EXACT 3-COVERS S′as follows:

S′(F∗) := {σ∈S:|δF∗(σ)|= 4}and F∗

ST (S′) := S′×T.

A direct computation reveals that the total objective value of the optimum solution for a graph

corresponding to a YES-instances of X3C is right as given in Equation (15).

6.2 Inapproximability of the MMST problem

Peleg and Reshef (1999, [23]) prove that the MMST problem

“cannot be approximated within a factor better than (1 + √5)/2, unless P=NP.”

Even recently, this result is usually cited when illustrating the complexity of the MMST prob-

lem ([9]).

In Section 3, using the UNTS to classify the large variety of similar tree spanner problems,

we were able to establish that in the case of unweighted graphs the following four problems

coincide:

•the MMST problem max, V ⊗V, dT(u,v)

dG(u,v),

•the problem max, E \T, dT(u,v)

dG(u,v),

•the problem (max, E \T, dT(u, v)), and

•the problem (max, E \T, dT(u, v) + w(e)).

It is a simple observation that in the case of unweighted graphs, for every fixed tree the objective

values of the first three tree spanner problems coincide and differ by one from the fourth one.

In particular, any constant inapproximability factor that is obtained for one of these problems

carries over to the other problems.

Now, Galbiati (2001, 2003 [12, 13]) investigatedthe problem (max, E \T, dT(u, v) + w(e)),

whichshedenotesthe MIN-MAX STRICTLY FUNDAMENTAL CYCLE BASIS (MMSFCB) prob-

lem. This culminates in the following theorem for unweighted graphs.

Theorem 28 ([12, 13]).The problem of finding in a uniform graph Ga spanning tree that is

optimal for (max, E \T, dT(u, v) + w(e)) cannot be approximated within 2−ǫ,∀ǫ > 0,

unless P=NP.

The above considerations enable us to identify the constant inapproximability factor of The-

orem 28 as a stronger inapproximability factor for the MINIMUM MAX-STRETCH SPANNING

TREE (MMST) problem, or max, V ⊗V, dT(u,v)

dG(u,v)in UNTS.

Corollary 29. The MINIMUM MAX-STRETCH SPANNING TREE problem cannot be approxi-

mated within a factor better than 2−ε,∀ǫ > 0, unless P=NP .

Note that another factor-2−εinapproximability result has been obtained for a problem

which appears much similar to (max, E, dT(u, v)). Although one could be tempted to use it

immediately for the MMST/MMSFCB problem, there is still a slight difference. In [16], there

are two different sets of edges involved: one are the candidate edges for choosing the spanning

tree, the others indicate for which sets of pairs (u, v)of vertices the term dT(u, v)shall be

evaluated for the objective function—a requirement graph. On the one hand, the proof in [16]

exploits this fact. On the other hand, such additional structures are beyond the scope of the tree

spanner problems that we consider in this paper.

7 Conclusions

We presented a unified notation for tree spanner (UNTS) problems. This allowed us to detect

that several tree spanner problems coincide. This is complemented by a number of example

graphs showing that no further coincidences exist. We even identified a tree spanner problem,

whose complexity status has been open before: P, V ⊗V, dT(u,v)

dG(u,v). For this problem, we

present an NP-hardness proof.

Moreover, the UNTS enabled us to build the bridge between the cycle bases perspective

and the tree spanner perspective on the very same problems. In particular, we establish that

the inapproximability result due to Galbiati ([12, 13])—initially obtained for the MIN-MAX

STRICTLY FUNDAMENTAL CYCLE BASIS (MMSFCB) problem—applies to the MINIMUM

MAX-STRETCH SPANNING TREE (MMST) problem, too, and outperforms the best inapprox-

imability result that was known in this context: 2−εcompared to 1+√5

2≈1.618.

Yet, it is by far beyond the scope of this paper to draw the complete map of (in-) approx-

imability results for tree spanner problems—occasionally even for several classes of graphs.

Nevertheless, when exploring this wide area of discrete mathematics, we hope the UNTS to

provide an accurate common language in order to prevent double work.

Acknowledgement

The authors like to thank the anonymous referees for their comments and remarks.

References

[1] N. Alon, R. M. Karp, D. Peleg, and D. B. West. A graph-theoretic game and its application

to the k-server problem. SIAM J. Comput., 24(1):78–100, 1995.

[2] C. Berge. The Theory of Graphs and its Applications. John Wiley & Sons, Inc., 1962.

[3] A. Brandst¨

adt, F. F. Dragan, H.-O. Le, and V. B. Le. Tree spanners on chordal graphs:

complexity and algorithms. Theor. Comput. Sci., 310(1-3):329–354, 2004.

[4] A. Brandst¨

adt, F. F. Dragan, H.-O. Le, V. B. Le, and R. Uehara. Tree spanners for bipartite

graphs and probe interval graphs. In H. L. Bodlaender, editor, WG, volume 2880 of Lecture

Notes in Computer Science, pages 106–118. Springer, 2003.

[5] L. Cai and D. G. Corneil. Tree spanners. SIAM J. Discrete Math., 8(3):359–387, 1995.

[6] D. M. Chickering, D. Geiger, and D. Heckerman. On finding a cycle basis with a shortest

maximal cycle. Inf. Process. Lett., 54(1):55–58, 1995.

[7] E. Dahlhaus, P. Dankelmann, W. Goddard, and H. C. Swart. MAD trees and distance-

hereditary graphs. Discrete Applied Mathematics, 131(1):151–167, 2003.

[8] N. Deo, M. Krishnomoorthy, and G. Prabhu. Algorithms for generating fundamental

cycles in a graph. ACM Transactions on Mathematical Software, 8(1):26–42, 1982.

[9] M. Elkin, Y. Emek, D. A. Spielman, and S.-H. Teng. Lower-stretch spanning trees. In

H. N. Gabow and R. Fagin, editors, STOC, pages 494–503. ACM, 2005.

[10] Y. Emek and D. Peleg. Approximating minimum max-stretch spanning trees on un-

weighted graphs. In J. I. Munro, editor, SODA, pages 254–263. SIAM, 2004.

[11] S. P. Fekete and J. Kremer. Tree spanners in planar graphs. Discrete Applied Mathematics,

108(1-2):85–103, 2001.

[12] G. Galbiati. On min-max cycle bases. In P. Eades and T. Takaoka, editors, ISAAC, volume

2223 of Lecture Notes in Computer Science, pages 116–123. Springer, 2001.

[13] G. Galbiati. On finding cycle bases and fundamental cycle bases with a shortest maximal

cycle. Inf. Process. Lett., 88(4):155–159, 2003.

[14] G. Galbiati and E. Amaldi. On the approximability of the minimum fundamental cycle

basis problem. In K. Jansen and R. Solis-Oba, editors, WAOA, volume 2909 of Lecture

Notes in Computer Science, pages 151–164. Springer, 2003.

[15] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of

NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.

[16] R. Hassin and A. Levin. Minimum restricted diameter spanning trees. In K. Jansen,

S. Leonardi, and V. V. Vazirani, editors, APPROX, volume 2462 of Lecture Notes in Com-

puter Science, pages 175–184. Springer, 2002.

[17] R. Hassin and A. Tamir. On the minimum diameter spanning tree problem. Inf. Process.

Lett., 53(2):109–111, 1995.

[18] J. D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph.

SIAM J. Comput., 16(2):358–366, 1987.

[19] T. C. Hu. Optimum communication spanning trees. SIAM J. Comput., 3(3):188–195,

1974.

[20] D. S. Johnson, J. K. Lenstra, and A. R. Kan. The complexity of the network design

problem. Networks, 8:279–285, 1978.

[21] T. Kavitha, K. Mehlhorn, D. Michail, and K. E. Paluch. A faster algorithm for minimum

cycle basis of graphs. In J. D´

ıaz, J. Karhum¨

aki, A. Lepist¨

o, and D. Sannella, editors,

ICALP, volume 3142 of Lecture Notes in Computer Science, pages 846–857. Springer,

2004.

[22] D. Kratsch, H.-O. Le, H. M¨

uller, E. Prisner, and D. Wagner. Additive tree spanners. SIAM

J. Discrete Math., 17(2):332–340, 2003.

[23] D. Peleg and E. Reshef. A variant of the arrow distributed directory with low average

complexity. In J. Wiedermann, P. van Emde Boas, and M. Nielsen, editors, ICALP, volume

1644 of Lecture Notes in Computer Science, pages 615–624. Springer, 1999.

[24] D. Peleg and D. Tendler. Low stretch spanning trees for planar graphs. Technical Report

MCS01-14, Weizmann Institute of Science, 2001.

[25] B. Y. Wu, K.-M. Chao, and C. Y. Tang. Approximation algorithms for the shortest total

path length spanning tree problem. Discrete Applied Mathematics, 105(1-3):273–289,

2000.

[26] B. Y. Wu, G. Lancia, V. Bafna, K.-M. Chao, R. Ravi, and C. Y. Tang. A polynomial-

time approximation scheme for minimum routing cost spanning trees. SIAM J. Comput.,

29(3):761–778, 1999.

Reports from the group

“Combinatorial Optimization and Graph Algorithms”

of the Department of Mathematics, TU Berlin

2007/22 Michael Elkin and Christian Liebchen and Romeo Rizzi: New Length Bounds for Cycle Bases

2007/19 Nadine Baumann and Sebastian Stiller: The Price of Anarchy of a Network Creation Game with

Exponential Payoff

2007/17 Christian Liebchen and Michael Schachtebeck and Anita Sch¨

obel and Sebastian Stiller and

Andr´

e Prigge: Computing Delay Resistant Railway Timetables

2007/03 Christian Liebchen and Gregor W¨

unsch and Ekkehard K¨

ohler and Alexander Reich and Romeo

Rizzi: Benchmarks for Strictly Fundamental Cycle Bases

2006/32 Romeo Rizzi and Christian Liebchen: A New Bound on the Length of Minimum Cycle Bases

2006/24 Christian Liebchen and Sebastian Stiller: Delay Resistant Timetabling

2006/08 Nicole Megow and Tjark Vredeveld: Approximation Results for Preemptive Stochastic Online

Scheduling

2006/07 Ekkehard K¨

ohler and Christian Liebchen and Romeo Rizzi and Gregor W¨

unsch: Reducing the

Optimality Gap of Strictly Fundamental Cycle Bases in Planar Grids

2006/05 Georg Baier and Thomas Erlebach and Alexander Hall and Ekkehard K¨

ohler and Heiko

Schilling: Length-Bounded Cuts and Flows

2005/30 Ronald Koch and Martin Skutella and Ines Spenke : Maximum k-Splittable Flows

2005/29 Ronald Koch and Ines Spenke : Complexity and Approximability of k-Splittable Flows

2005/28 Stefan Heinz and Sven O. Krumke and Nicole Megow and J¨

org Rambau and Andreas Tuch-

scherer and Tjark Vredeveld: The Online Target Date Assignment Problem

2005/18 Christian Liebchen and Romeo Rizzi: Classes of Cycle Bases

2005/11 Rolf H. M¨

ohring and Heiko Schilling and Birk Sch¨

utz and Dorothea Wagner and Thomas Will-

halm: Partitioning Graphs to Speed Up Dijkstra’s Algorithm.

2005/07 Gabriele Di Stefano and Stefan Krause and Marco E. L¨

ubbecke and Uwe T.Zimmermann: On

Minimum Monotone and Unimodal Partitions of Permutations

2005/06 Christian Liebchen: A Cut-based Heuristic to Produce Almost Feasible Periodic Railway

Timetables

2005/03 Nicole Megow, Marc Uetz, and Tjark Vredeveld: Models and Algorithms for Stochastic Online

Scheduling

2004/37 Laura Heinrich-Litan and Marco E. L¨

ubbecke: Rectangle Covers Revisited Computationally

2004/35 Alex Hall and Heiko Schilling: Flows over Time: Towards a more Realistic and Computationally

Tractable Model

2004/31 Christian Liebchen and Romeo Rizzi: A Greedy Approach to Compute a Minimum Cycle Bases

of a Directed Graph

2004/27 Ekkehard K¨

ohler and Rolf H. M¨

ohring and Gregor W¨

unsch: Minimizing Total Delay in Fixed-

Time Controlled Traffic Networks

2004/26 Rolf H. M¨

ohring and Ekkehard K¨

ohler and Ewgenij Gawrilow and Bj¨

orn Stenzel: Conflict-free

Real-time AGV Routing

2004/21 Christian Liebchen and Mark Proksch and Frank H. Wagner: Performance of Algorithms for

Periodic Timetable Optimization

2004/20 Christian Liebchen and Rolf H. M¨

ohring: The Modeling Power of the Periodic Event Scheduling

Problem: Railway Timetables — and Beyond

2004/19 Ronald Koch and Ines Spenke: Complexity and Approximability of k-splittable flow problems

2004/18 Nicole Megow, Marc Uetz, and Tjark Vredeveld: Stochastic Online Scheduling on Parallel Ma-

chines

2004/09 Marco E. L¨

ubbecke and Uwe T. Zimmermann: Shunting Minimal Rail Car Allocation

2004/08 Marco E. L¨

ubbecke and Jacques Desrosiers: Selected Topics in Column Generation

2003/050 Berit Johannes: On the Complexity of Scheduling Unit-Time Jobs with OR-Precedence Con-

straints

2003/49 Christian Liebchen and Rolf H. M¨

ohring: Information on MIPLIB’s timetab-instances

2003/48 Jacques Desrosiers and Marco E. L¨

ubbecke: A Primer in Column Generation

2003/47 Thomas Erlebach, Vanessa K¨

a¨

ab, and Rolf H. M¨

ohring: Scheduling AND/OR-Networks on

Identical Parallel Machines

2003/43 Michael R. Bussieck, Thomas Lindner, and Marco E. L¨

ubbecke: A Fast Algorithm for Near Cost

Optimal Line Plans

2003/42 Marco E. L¨

ubbecke: Dual Variable Based Fathoming in Dynamic Programs for Column Gener-

ation

2003/37 S´

andor P. Fekete, Marco E. L¨

ubbecke, and Henk Meijer: Minimizing the Stabbing Number of

Matchings, Trees, and Triangulations

2003/25 Daniel Villeneuve, Jacques Desrosiers, Marco E. L¨

ubbecke, and Franc¸ois Soumis: On Compact

Formulations for Integer Programs Solved by Column Generation

2003/24 Alex Hall, Katharina Langkau, and Martin Skutella: An FPTAS for Quickest Multicommodity

Flows with Inflow-Dependent Transit Times

2003/23 Sven O. Krumke, Nicole Megow, and Tjark Vredeveld: How to Whack Moles

2003/22 Nicole Megow and Andreas S. Schulz: Scheduling to Minimize Average Completion Time Re-

visited: Deterministic On-Line Algorithms

2003/16 Christian Liebchen: Symmetry for Periodic Railway Timetables

2003/12 Christian Liebchen: Finding Short Integral Cycle Bases for Cyclic Timetabling

Reports may be requested from: Sekretariat MA 6–1

Fakultt II – Institut fr Mathematik

TU Berlin

Straße des 17. Juni 136

D-10623 Berlin – Germany

e-mail: [email protected]n.DE

Reports are also available in various formats from

http://www.math.tu-berlin.de/coga/publications/techreports/

and via anonymous ftp as

ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Report-number-year.ps