Julien Baste
email: julien.baste@uni-ulm.de

Didem Gözüpek
email: didem.gozupek@gtu.edu.tr

Christophe Paul
email: paul@lirmm.fr

Ignasi Sau
email: sau@lirmm.fr

Mordechai Shalom
email: cmshalom@telhai.ac.il

Dimitrios M Thilikos

Parameterized complexity of finding a spanning tree with minimum reload cost diameter *

Keywords: reload cost problems, minimum diameter spanning tree, parameterized complexity, FPT algorithm, treewidth, dynamic programming

 proved that the problem can be solved in polynomial time on graphs with ∆ 3, and Galbiati (2008) proved that it is NP-hard if ∆ 4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if ∆ 3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that Diameter-Tree is in XP and W[1]-hard parameterized by the treewidth plus ∆.

Introduction

Numerous network optimization problems can be modeled by edge-colored graphs. Wirth and Steffan introduced in [START_REF] Wirth | Reload cost problems: Minimum diameter spanning tree[END_REF] the concept of reload cost, which refers to the cost that arises in an edge-colored graph while traversing a vertex via two consecutive edges of different colors. The value of the reload cost depends on the colors of the traversed edges. Although the reload cost concept has many important applications in telecommunication networks, transportation networks, and energy distribution networks, it has surprisingly received attention only recently.

In heterogeneous communication networks, routing requires switching among different technologies such as cables, fibers, and satellite links. Due to data conversion between incompatible subnetworks, this switching causes high costs, largely outweighing the cost of routing the packets within each subnetwork. The recently popular concept of vertical handover [START_REF] Desset | Energy savings for wireless terminals through smart vertical handover[END_REF], which allows a mobile user to have undisrupted connection during transitioning between different technologies such as 3G (third generation) and wireless local area network (WLAN), constitutes another application area of the reload cost concept. Even within the same technology, switching between different service providers incurs switching costs. Another paradigm that has received significant attention in the wireless networks research community is cognitive radio networks (CRN), a.k.a. dynamic spectrum access networks. Unlike traditional wireless technologies, CRNs operate across a wide frequency range in the spectrum and frequently require frequency switching; therefore, the frequency switching cost is indispensable and of paramount importance. Many works in the CRNs literature focused on this frequency switching cost from an application point of view (for instance, see [1, 3-5, 14, 21, 31]) by analyzing its various aspects such as delay and energy consumption. Operating in a wide range of frequencies is indeed a property of not only CRNs but also other 5G technologies. Hence, applications of the reload cost concept in communication networks continuously increase. In particular, the energy consumption aspect of this switching cost is especially important in the recently active research area of green networks, which aim to tackle the increasing energy consumption of information and communication technologies [START_REF] Bianzino | A survey of green networking research[END_REF][START_REF] Celik | Green cooperative spectrum sensing and scheduling in heterogeneous cognitive radio networks[END_REF].

The concept of reload cost also finds applications in other networks such as transportation networks and energy distribution networks. For instance, a cargo transportation network uses different means of transportation. The loading and unloading of cargo at junction points is costly and this cost may even outweigh the cost of carrying the cargo from one point to another [START_REF] Galbiati | The complexity of a minimum reload cost diameter problem[END_REF]. In energy distribution networks, reload costs can model the energy losses that occur at the interfaces while transferring energy from one type of carrier to another [START_REF] Galbiati | The complexity of a minimum reload cost diameter problem[END_REF].

Recent work in the literature focused on numerous problems related to the reload cost concept: the minimum reload cost cycle cover problem [START_REF] Galbiati | On minimum reload cost cycle cover[END_REF], the problems of finding a path, trail or walk with minimum total reload cost between two given vertices [START_REF] Gourvès | The minimum reload s-t path, trail and walk problems[END_REF], the problem of finding a spanning tree that minimizes the sum of reload costs of all paths between all pairs of vertices [START_REF] Gamvros | Reload cost trees and network design[END_REF], various path, tour, and flow problems related to reload costs [START_REF] Amaldi | On minimum reload cost paths, tours, and flows[END_REF], the minimum changeover cost arborescence problem [START_REF] Galbiati | On minimum changeover cost arborescences[END_REF][START_REF] Gözüpek | Parameterized complexity of the MINCCA problem on graphs of bounded decomposability[END_REF][START_REF] Gözüpek | Constructing minimum changeover cost arborescenses in bounded treewidth graphs[END_REF][START_REF] Gözüpek | On the complexity of constructing minimum changeover cost arborescences[END_REF], and problems related to finding a proper edge coloring of the graph so that the total reload cost is minimized [START_REF] Gözüpek | Complexity of edge coloring with minimum reload/changeover costs[END_REF].

The work in [START_REF] Wirth | Reload cost problems: Minimum diameter spanning tree[END_REF], which introduced the concept of reload cost, focused on the following problem, called Minimum Reload Cost Diameter Spanning Tree (Diameter-Tree for short), and which is the one we study in this paper: given an undirected graph G pV, Eq with a (non necessarily proper) edge-coloring χ : EpGq Ñ X and a reload cost function c : X 2 Ñ N 0 , find a spanning tree of G with minimum diameter with respect to the reload costs (see Section 2 for the formal definitions).

This problem has important applications in communication networks, since forming a spanning tree is crucial for broadcasting control traffic such as route update messages. For instance, in a multi-hop cognitive radio network where a frequency is assigned to each wireless link depending on availability of spectrum bands, delay-aware broadcasting of control traffic necessitates the forming of a spanning tree by taking the delay arising from frequency switching at every node into account. Cognitive nodes send various control information messages to each other over this spanning tree. A spanning tree with minimum reload cost diameter in this setting corresponds to a spanning tree in which the maximum frequency switching delay between any two nodes on the tree is minimized. Since control information is crucial and needs to be sent to all other nodes in a timely manner, ensuring that the maximum delay is minimum is vital in a cognitive radio network.

Wirth and Steffan [START_REF] Wirth | Reload cost problems: Minimum diameter spanning tree[END_REF] proved that Diameter-Tree is inapproximable within a factor better than 3 (in particular, it is NP-hard), even on graphs with maximum degree 5. They also provided a polynomial-time exact algorithm for the special case where the maximum degree is 3 and the reload costs satisfy the triangle inequality. Galbiati [START_REF] Galbiati | The complexity of a minimum reload cost diameter problem[END_REF] showed stronger hardness results for this problem, by proving that even on graphs with maximum degree 4, the problem cannot be approximated within a factor better than 2 if the reload costs do not satisfy the triangle inequality, and cannot be approximated within any factor better than 5{3 if the reload costs satisfy the triangle inequality. The complexity of Diameter-Tree (in the general case) on graphs with maximum degree 3 was left open.

Our results. In this article we initiate a systematic study of the complexity of the Diameter-Tree problem, with special emphasis on its parameterized complexity for several choices of the parameters. Namely, we consider any combination of the parameters k (the cost of a solution), tw (the treewidth of the input graph), and ∆ (the maximum degree of the input graph). We would like to note that these parameters have practical importance in communication networks. Indeed, besides the natural parameter k, whose relevance is clear, many networks that model real-life situations appear to have small treewidth [START_REF] Jensen | Bayesian Networks and Decision Graphs[END_REF][START_REF] Lauritzen | Local computations with probabilities on graphical structures and their application to expert systems[END_REF]. On the other hand, the degree of a node in a network is related to its number of transceivers, which are costly devices in many different types of networks such as optical networks [START_REF] Konda | Algorithm for traffic grooming in optical networks to minimize the number of transceivers[END_REF]. For this reason, in practice the maximum degree of a network usually takes small values.

Before elaborating on our results, a summary of them can be found in We first prove, by a reduction from 3-Sat, that Diameter-Tree is NP-hard on outerplanar graphs (which have treewidth at most 2) with only one vertex of degree greater than 3, even with three different costs that satisfy the triangle inequality, and k 9. Note that, in the case where the costs satisfy the triangle inequality, having only one vertex of degree greater than 3 is best possible, as if all vertices have degree at most 3, the problem can be solved in polynomial time [START_REF] Wirth | Reload cost problems: Minimum diameter spanning tree[END_REF]. Note also that the bound on the treewidth is best possible as well, since the problem is trivially solvable on graphs of treewidth 1, i.e., on forests.

Toward investigating the border of tractability of the problem with respect to treewidth, we exhibit a polynomial-time algorithm on a relevant subclass of the graphs of treewidth at most 2: cactus graphs. This algorithm is quite involved and, in a nutshell, processes in a bottom-up manner the block tree of the given cactus graph, and uses at each step of the processing an algorithm that solves 2-Sat as a subroutine.

Back to hardness results, we also prove, by a reduction from a restricted version of 3-Sat, that Diameter-Tree is NP-hard on graphs with ∆ ¤ 3, even with only two different costs, k 0, and a bounded number of colors. In particular, this settles the complexity of the problem on graphs with ∆ ¤ 3 in the general case where the triangle inequality is not necessarily satisfied, which had been left open in previous work [START_REF] Galbiati | The complexity of a minimum reload cost diameter problem[END_REF][START_REF] Wirth | Reload cost problems: Minimum diameter spanning tree[END_REF].

Note that ∆ ¤ 3 is best possible, as Diameter-Tree can be easily solved on graphs with ∆ ¤ 2.

As our last NP-hardness reduction, we prove, by a reduction from Partition, that the Diameter-Tree problem is NP-hard on planar graphs with tw ¤ 3 and ∆ ¤ 3.

The above hardness results imply that the Diameter-Tree problem is para-NP-hard for any combination of two of the three parameters k, tw, and ∆. On the positive side, we show that Diameter-Tree is FPT parameterized by the three of them, by using a (highly nontrivial) dynamic programming algorithm on a tree decomposition of the input graph.

Since our para-NP-hardness reduction with parameter tw ∆ is from Partition, which is a typical example of a weakly NP-complete problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-completeness[END_REF], a natural question is whether Diameter-Tree, with parameter tw ∆, is para-NP-hard, XP, W [START_REF] Agarwal | Dynamic spectrum access for energy-constrained CR: Single channel versus switched multichannel[END_REF]-hard, or FPT when the reload costs are polynomially bounded by the size of the input graph. We manage to answer this question completely: we show that in this case the problem is in XP (hence not para-NP-hard) and W [START_REF] Agarwal | Dynamic spectrum access for energy-constrained CR: Single channel versus switched multichannel[END_REF]-hard parameterized by tw ∆. The W[1]-hardness reduction is from the Unary Bin Packing problem parameterized by the number of bins, proved to be Wr1s-hard by Jansen et al. [START_REF] Jansen | Bin packing with fixed number of bins revisited[END_REF].

Altogether, our results provide an accurate picture of the (parameterized) complexity of the Diameter-Tree problem.

Organization of the paper. We start in Section 2 with some brief preliminaries about graphs, the Diameter-Tree problem, parameterized complexity, and tree decompositions. In Section 3 we provide the para-NP-hardness results. In Section 4 we present the polynomial-time algorithm on cactus graphs, and in Section 5 we present the FPT algorithm on general graphs parameterized by k tw ∆. In Section 6 we focus on the case where the reload costs are polynomially bounded. Finally, we conclude the article in Section 7.

Preliminaries

Graphs and sets. We use standard graph-theoretic notation, and we refer the reader to [START_REF] Diestel | Graph Theory[END_REF] for any undefined term. Given a graph G and a set S V pGq, we define adj G pSq to be the set of edges of G that intersect S, i.e., those edges that have at least one endpoint in S. We also define N G rSs S tx | hy S : tx, yu EpGqu. Given a graph G and a vertex v V pGq with exactly two neighbors u and w, dissolving v is the operation that consists in removing v, tu, vu, and tv, wu and adding the edge tu, wu. For a graph G and an edge e EpGq, we denote G ¡ e pV pGq, EpGqzteuq. Given two integers i and j with i ¤ j, we use ri, js to denote the set of integers k such that i ¤ k ¤ j. We use the shorthand notation ris for r1, is.

Reload costs and definition of the problem. For reload costs, we follow the notation and terminology defined by [START_REF] Wirth | Reload cost problems: Minimum diameter spanning tree[END_REF]. We consider edge-colored graphs G pV, Eq, where the colors are taken from a finite set X and the coloring function is χ : EpGq Ñ X. The reload costs are given by a nonnegative function c : X 2 Ñ N 0 , which we assume to be symmetric. The cost of traversing two incident edges e 1 , e 2 is cpe 1 , e 2 q : cpχpe 1 q, χpe 2 qq. The reload cost cpP q of a path P of length with edges e 1 , e 2 , . . . , e is cpP q : ° i2 cpe i¡1 , e i q.

Note that the reload cost of a path consisting of one edge is zero. Throughout this work, the terms distance, diameter and eccentricity will be used only with respect to this reload cost measure. The (reload cost) distance between two vertices u, v in a graph G is dist c G pu, vq mintcpP q | P is a path between u and v in Gu. The (reload cost)

eccentricity of a vertex u in a graph G is c G puq maxtdist c G pu, vq | v V pGqu. The (reload cost) diameter of a graph G is diam c pGq : maxt c G puq | u V pGqu.
For notational convenience we assume that the edge-coloring function χ and the reload cost function c are clear from the context and omit the superscript c in the last three definitions.

The problem we study in this paper is defined as follows:

Minimum Reload Cost Diameter Spanning Tree (Diameter-Tree)

Input: A graph G pV, Eq with an edge-coloring χ and a reload cost function c. Output: A spanning tree T of G minimizing diampT q.

If for every three distinct edges e 1 , e 2 , e 3 of G incident to the same node, it holds that cpe 1 , e 3 q ¤ cpe 1 , e 2 q cpe 2 , e 3 q, we say that the reload cost function c satisfies the triangle inequality. This assumption is sometimes used in practical applications [START_REF] Wirth | Reload cost problems: Minimum diameter spanning tree[END_REF].

Throughout the paper, we denote by n, ∆, and tw the number of vertices, the maximum degree, and the treewidth of the input graph, respectively. When we consider the (parameterized) decision version of the Diameter-Tree problem, we denote by k the desired cost of a solution.

Parameterized complexity. We refer the reader to [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] for basic background on parameterized complexity, and we recall here only some basic definitions. A parameterized problem is a language L Σ ¦ ¢N. The number k is termed the parameter of the instance I px, kq Σ ¦ ¢ N.

An algorithm for a parameterized problem L is an algorithm that decides whether an input instance I px, kq is in L. Such an algorithm is an FPT (resp. XP) algorithm if its running time is bounded by f pkq ¤ |I| c (resp. f pkq ¤ |I| gpkq ) for some computable functions f, g and some constant c. The class FPT (resp. XP) is the class of all parameterized problems for which an FPT (resp. XP) algorithm exists. Clearly, FPT XP. A parameterized problem that is in FPT is termed fixed-parameter tractable. The Vertex Cover problem, parameterized by the size of the solution, is in FPT. The Clique problem, parameterized by the size of the solution, is in XP.

A parameterized problem is para-NP-hard if it is NP-hard when the value of its parameter is bounded by some constant. The Vertex Coloring problem parameterized by the number of colors is para-NP-hard. Note that, unless P NP, a para-NP-hard problem cannot be in XP, hence it cannot be FPT either.

Within parameterized problems, the class W[1] may be seen as the parameterized equivalent to the class NP of classical optimization problems. Without entering into details (see [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] for the formal definitions), if a parameterized problem is W[1]-hard then this problem is unlikely to be in FPT. The Clique problem parameterized by the size of the solution is the canonical example of a W [START_REF] Agarwal | Dynamic spectrum access for energy-constrained CR: Single channel versus switched multichannel[END_REF]-hard problem. To transfer W[1]-hardness from one problem to another, one uses a parameterized reduction, which given an input I px, kq of the source problem, computes an equivalent instance I I px I , k I q of the target problem in time f pkq ¤ |I| c , where f is a computable function, c is a constant, and k I is bounded by a function depending only on k.

Tree decompositions. A tree decomposition of a graph G is a pair D pY, X q, where Y is a tree and X tX t | t V pY qu is a collection of subsets of V pGq such that:

• tV pY q X t V pGq,
• for every edge tu, vu E, there is a t V pY q such that tu, vu X t , and • for each tx, y, zu V pY q such that z lies on the unique path between x and y in Y , X x X y X z .

We call the vertices of Y nodes of D and the sets in X bags of D. The width of the tree decomposition D pY, X q is max tV pY q |X t | ¡ 1. The treewidth of G, denoted by twpGq, is the smallest integer w such that there exists a tree decomposition of G of width w.

Nice tree decompositions. Let D pY, X q be a tree decomposition of G, r be a vertex of Y designated as its root, and G tG t | t V pY qu be a collection of subgraphs of G, indexed by the vertices of Y . A triple pD, r, Gq is nice if:

• every node of D has at most two children in Y ,

• for every leaf t of Y except r, X t r and G t pr, rq (t is termed a leaf node in this case),

• X r r and G r G,

• if t V pY q has two children t I and t P , then X t X t I X t P, and EpG t IqEpG t Pq r (t is termed a join node in this case),

• if t V pT q has exactly one child t I one of the following holds: -X t X t I tv insert u for some v insert X t I and G t pV pG t Iq tv insert u, EpG t Iqq (t is termed a vertex-introduce node and v insert is the insertion vertex of X t ), -X t X t I and G t pG t I, EpG t Iq te insert uq where e insert is an edge of G with endpoints in X t . In (t is termed an edge-introduce node and e insert is the insertion edge of X t ), -X t X t Iztv forget u for some v forget X t I and G t G t I (t is termed a forget node and v forget is the forget vertex of X t ).

The notion of a nice triple defined above is essentially the same as the one of nice tree decomposition in [START_REF] Cygan | Solving connectivity problems parameterized by treewidth in single exponential time[END_REF] (which is in turn an enhancement of the original one, introduced in [START_REF] Kloks | Treewidth[END_REF]). As already argued in [START_REF] Cygan | Solving connectivity problems parameterized by treewidth in single exponential time[END_REF][START_REF] Kloks | Treewidth[END_REF], it is possible to transform in polynomial time a

given tree decomposition to a nice triple pD, r, Gq such that D has the same width as the given tree decomposition.

Transfer triples and their fusion. For a graph G and a subset R of its vertices, denote by R G the set of all edges and vertices of G except the edges incident to R, i.e., R G V pGq EpGqzadj G pRq. A triple pF, R, αq where F is a forest, R V pFq, and α : R ¢ R F Ñ r0, ks tuu is a transfer triple if αpv, aq $ u if and only if v and a are in the same connected component of F . See Figure 1 for an illustration. Intuitively, the function α will indicate the "cost of transferring" from v to a in F for each pair pv, aq.

Let pF 1 , R, α 1 q and pF 2 , R, α 2 q be two transfer triples where F 1 and F 2 are edgedisjoint and their union F is a forest. Let also β : adj F 1 pRq ¢ adj F 2 pRq Ñ r0, ks tuu. We require a function α 1 β α 2 : R ¢ R F Ñ r0, ks tuu that builds the transferring costs of moving in F by taking into account the corresponding transferring costs in F 1 and F 2 .

The values of α 1 β α 2 are defined as follows:

Let pv, aq R ¢ R F . Let P be the path in F between v and a and let V pPq tv 0 , . . . , v r u, ordered in the way these vertices appear in P and assuming that v 0 v. To simplify notation, we assume that tv 0 , v 1 u is an edge of F 1 (otherwise, exchange the roles of F 1 and F 2 ). Given i rr ¡ 1s, we define e ¡ i (resp. e i ) as the edge incident to v i that appears before (resp. after) v i when traversing P from v to a. We define the set of indices

I ti | e ¡
i and e i belong to different sets of tEpF 1 q, EpF 2 quu. Let I ti 1 , . . . , i q u, where numbers are ordered in increasing order and we also set i 0 0.

Then we set

α 1 β α 2 pv, aq ḩr0,t q¡1 2 us α 1 pv 2i h , v 2i h 1 q ḩr0,t q¡2 2 us α 2 pv 2i h 1 , v 2i h 2 q ḩrqs βpe ¡ i h , e i h q α pq mod 2q 1 pv iq , aq.
Roughly speaking, α 1 β α 2 pv, aq is the cost of the path P from v to a in F calculated as the sum of the cost of each connected component, provided by α 1 and α 2 , of P F 1 and P F 2 together with the sum of the costs, provided by β, of each transition from

F 1 to F 2 and F 2 to F 1 used by P .
Satisfiability. An instance of 3-Sat is a boolean formula ϕ with n variables x 1 , . . . , x n and m clauses where each clause contains at most three literals, and a literal is an occurence of a variable or its negation. The goal is to decide whether there is a truth assignment of the variables that satisfies all the clauses. A clause is satisfied if and only if one of its literals is set to true by the assignment. We can assume without loss of generality that every variable occurs at least once positively and at least once negatively. Indeed, otherwise one can set the truth assignment of this variable appropriately and remove from the formula all the clauses in which this variable occurs.

The restriction of 3-Sat to formulas where each variable occurs in at most three clauses was proved to be NP-complete by Tovey [START_REF] Tovey | A simplified NP-complete satisfiability problem[END_REF]. It is worth mentioning that one needs to allow for clauses of size two or three, as if all clauses have size exactly three, then it turns out that all instances are satisfiable [START_REF] Tovey | A simplified NP-complete satisfiability problem[END_REF].

When working with this restriction, we may also assume:

Every variable occurs exactly three times in the formula ϕ.

Indeed, let x be a variable occurring exactly two times in ϕ, once positively and once negatively. We obtain a new formula ϕ I from ϕ by adding a new variable y and two clauses x y and y y. Clearly ϕ and ϕ I are equivalent, and both x and y occur exactly three times in ϕ I . Applying these operations exhaustively results in an equivalent formula in which every variable occurs exactly three times.

3 Para-NP-hardness results

We start with the para-NP-hardness result for the parameter k tw.

Theorem 1. The Diameter-Tree problem is NP-hard on outerplanar graphs with only one vertex of degree larger than 3, even with three different costs that satisfy the triangle inequality, and k 9. Since outerplanar graphs have treewidth at most 2, in particular, Diameter-Tree is para-NP-hard when parameterized by k tw.

Proof. We present a reduction from 3-Sat. Given a formula ϕ with n variables and m clauses, we create an instance pG, χ, cq of Diameter-Tree as follows. We may assume that no clause of ϕ contains a variable and its negation. Consult Figure 2 for the following construction. The graph G contains a distinguished vertex r and, and a clause gadget for every clause. The clause gadget C j corresponding to the clause c j p 1 2 3 q, consists of three vertices v j 1 , v j 2 , v j 3 and five edges tr, v j 1 u, tr, v j 2 u, tr, v j 3 u, tv j 1 , v j 2 u, and tv j 2 , v j 3 u. This completes the construction of G. Note that G does not depend on the formula ϕ except for the number of clause gadgets, and that it is an outerplanar graph with only one vertex of degree greater than 3, as required.

We proceed with the description of the coloring χ and the cost function c. For simplicity, we associate a distinct color with each edge of G, and thus, with slight abuse of notation, it is enough to describe the cost function c for every pair of incident edges of G, as we consider symmetric cost functions. We set cpe 1 , e 2 q 6 9 8 9 7

10 if e 1 tr,

v j 1 i 1 u, e 2 tr, v j 2 i 2 u and i 1 i 2 , 5 if e 1 tr, v j 1 i 1 u, e 2 tr, v j 2 i 2 u and i 1 i 2 , and 1 otherwise.
Note that this cost function satisfies the triangle inequality since the reload costs between edges incident to r are 5 and 10, and the reload costs between edges incident to other vertices are 1. We claim that ϕ is satisfiable if and only if G contains a spanning tree with diameter at most 9. Since r is a cut vertex and every clause gadget is a connected component of G ¡ r, in every spanning tree, the vertices of C j together with r induce a tree with four vertices. Moreover, the reload cost of a path from r to any leaf of this tree is at most 2. Therefore, the diameter of any spanning tree is at most 4 plus the maximum reload cost incurred at r by a path of T .

C j v j 1 v j 2 v j
Assume first that ϕ is satisfiable, and let ψ be a satisfying assignment of ϕ. We now construct a spanning tree T of G with diampT q ¤ 9. For every clause c j , the tree T j is the tree spanning C j and containing exactly one edge incident to r where the other endpoint of this edge is a literal of c j that is set to true by ψ. T is the union of all the trees T j constructed in this way. The reload cost incurred at r by any path of T traversing it is at most 5, since we never choose a literal and its negation. Therefore, diampT q ¤ 9.

Conversely, let T be a spanning tree of G with diampT q ¤ 9. Then, the reload cost incurred at r by any path traversing it is at most 5 since otherwise diampT q ¥ 10. For every j rms, let T j be the subtree of T induced by C j and let tr, v j i j u be one of the edges incident to r in T j . We note that for any pair of clauses c j 1 , c j 2 we have i j 1 $ i j 2 , since otherwise a path using these two edges would incur a cost of 10 at r. The variable in the literal i j is set by ψ so that i j is true. All the other variables are set to an arbitrary value by ψ. Note that ψ is well-defined, since we never encounter a literal and its negation during the assignment process. It follows that ψ is a satisfying assignment of ϕ.

We proceed with the para-NP-hardness result for the parameter k ∆.

Theorem 2. The Diameter-Tree problem is NP-hard on graphs with ∆ ¤ 3, even with two different costs, k 0, and a bounded number of colors. In particular, it is para-NP-hard parameterized by k ∆.

Proof. We present a reduction from the restriction of 3-Sat to formulae that satisfy property . We recall that property states that each variable occurs exactly three times in the given formula ϕ of 3-Sat and each variable occurs at least once positively and at least once negatively in ϕ.

Given a formula ϕ with n variables and m clauses, we create an instance pG, χ, cq of Diameter-Tree with ∆pGq ¤ 3 as follows. Let x 1 , . . . , x n be the variables of ϕ. For every i rns, G contains a variable gadget consisting of five vertices u i , v i , p i , r i , n i and five edges tu i , v i u , tv i , p i u , tp i , r i u , tr i , n i u , tn i , v i u (see Figure 3(a)). For every i rn¡1s, G contains the edge tu i , u i 1 u. G consists of a vertex c j for every j rms. For each variable x i , the vertex p i (resp. n i ) is connected to one of the vertices c j corresponding to a clause of ϕ in which x i appears positively (resp. negatively), and r i is connected to the vertex corresponding to the remaining clause in which x i appears (positively or negatively). This completes the construction of G. Note that ∆pGq ¤ 3 as required.

We now define the coloring χ and the cost function c. The color set X is r9s. For i rns, χptp i , r i uq 1 and χptr i , n i uq 2, and all edges incident to u i or v i have color 3. For j rms, we color the edges incident to c j using distinct colors from r4, 9s. Edges corresponding to positive (resp. negative) occurrences get colors from r4, 6s (resp. r7, 9s) (see Figure 3(b)). We set cp1, 2q 1, cp1, iq 1 for every i r4, 6s, cp2, iq 1 for every i r7, 9s, and cpi, jq 1 for every pair of distinct colors i, j r4, 9s. All other costs are set to 0. Figure 3: (a) Graph G described in the reduction of Theorem 2 for the formula ϕ px 1 x 2 x 3 q px 1 x 4 q px 3 x 4 q px 1 x 2 x 3 q px 2 x 4 q. The vertices p i , r i , n i corresponding to positive (resp. negative) occurrences are depicted with circles (resp. squares). An assignment satisfying ϕ is given by x 1 x 2 1 and x 3 x 4 0, and a solution spanning tree T with diameter 0 is emphasized with thicker edges. (b) The (possible) colors associated with each edge of G correspond to the (blue) numbers.

p 1 r 1 n 1 v 1 u 1 p 2 r 2 n 2 v 2 v 3 v 4 u 2 u 3 u 4 p 3 r 3 n 3 p 4 r 4 n 4 c 1 c 2 c 3 c 4 c 5 (a) (b) u i v i p i r i n i
We now show that ϕ is satisfiable if and only if G contains a spanning tree with reload cost diameter 0. Assume first that ϕ is satisfiable, and let ψ be a satisfying assignment of ϕ. We construct a spanning tree T of G with diameter 0 as follows. For every i rns, the tree T contains all the edges incident to u i and v i . If variable x i is set to true (resp. false) by ψ, T contains the edge tr i , n i u (resp. tp i , r i uq. For j rms, the tree T contains one of the edges incident c j that corresponds to a literal satisfying the j-th clause. It can be easily checked that T is a spanning tree of G with diampT q ¤ 0 (see Figure 3(a)).

Conversely, let T be a spanning tree of G with diampT q 0. Since the cost associated with any pair of distinct colors from r4, 9s is 1, it follows that c j is a leaf of T , for j rms. Therefore, the variable gadgets need to be connected in T via the vertices u i , implying that all the edges incident to u i belong to T for every i rns. Furthermore, T contains exactly three out of the four edges of the 4-cycle induced by tv i , p i , r i , n i u. Since cp1, 2q 1 and diampT q 0, the missing edge is either tp i , r i u or tr i , n i u. We define an assignment ψ of the variables x 1 , . . . , x n as follows. The variable x i is set to true by ψ if and only if the edge tr i , n i u belongs to T . We claim that ψ satisfies ϕ. Indeed, let c j be a vertex in G. Since c j is a leaf of T , it is connected exactly to one of the vertices p i , r i , n i for some i rns. Suppose that the edge e incident to c j in T corresponds to a positive occurrence of x i , the other case being symmetric. Then, e is one of tc j , p i u , tc j , r i u. In both cases, if the edge tp i , r i u were in T , this edge together with tc j , p i u or tc j , r i u would incur a cost of 1 in T , contradicting the hypothesis that diampT q 0. Therefore, the edge tp i , r i u cannot be in T , implying that the edge tr i , n i u must be in T . According to the definition of the assignment ψ, this implies that variable x i is set to true in ψ, and therefore the c-th clause of ϕ is satisfied by the variable x i .

Note that in the above reduction the cost function c does not satisfy the triangle inequality at vertices p i or n i for i rns, and recall that this is unavoidable since otherwise the problem would be polynomial [START_REF] Wirth | Reload cost problems: Minimum diameter spanning tree[END_REF]. It is worth mentioning that using the ideas in the proof of [START_REF] Gözüpek | Parameterized complexity of the MINCCA problem on graphs of bounded decomposability[END_REF]Theorem 4 of the full version] it can be proved that the Diameter-Tree problem is also NP-hard on planar graphs with ∆ ¤ 4, k 0, and a bounded number of colors; we omit the details here.

Finally, we present the para-NP-hardness result for the parameter tw ∆.

Theorem 3. The Diameter-Tree problem is NP-hard on planar graphs with tw ¤ 3 and ∆ ¤ 3. In particular, it is para-NP-hard parameterized by tw ∆.

Proof. We present a reduction from the Partition problem, which is a typical example of a weakly NP-complete problem [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-completeness[END_REF]. An instance of Partition is a multiset S ta 1 , a 2 , . . . , a n u of n positive integers, and the objective is to decide whether S can be partitioned into two subsets S 1 and S 2 such that °xS be the graph constructed so far. We then define G to be the graph obtained from two disjoint copies of G I by adding an edge between both roots. Note that G is a planar graph with ∆pGq 3 and twpGq 3. (The claimed bound on the treewidth can be easily seen by building a path decomposition of G with consecutive bags of the form

tu I i¡1 , d I i¡1 , u i , d i u, tu i , d i , m i , u I i u, td i , m i , u I i , m I i u, td i , u I i , m I i , d I i u, . . ..) r 1 a 1 a 1 a 1 a 1 a n a n r 2 u 2 u 2 d 2 d 2 m 2 m 2 a n a n a 2 a 2 0 0 0 0 0 0 0 0 B+1 B+1 B+1 B+1 0 0 0 0 0 0 B+1 B+1 H 2 P d P u
Figure 4: Graph G built in the reduction of Theorem 3, where the reload costs are depicted (in blue) at the angle between the two corresponding edges. For better visibility, not all costs and vertex labels are depicted. The typical shape of a solution spanning tree is highlighted with thicker edges.

Let us now define the coloring χ and the cost function c. Again, for simplicity, we associate a distinct color with each edge of G, and thus it is enough to describe the cost function c for every pair of incident edges of G. We define the costs for one of the copies of G I , and the same costs apply to the other copy. For every edge e being either tu I i , u i 1 u or td I i , d i 1 u, for 1 ¤ i ¤ n ¡ 1, we set cpe, e I q 0 for each of the four edges e I incident with e. For every edge e tm i , m I i u, for 1 ¤ i ¤ n, we set cptu i , m i u, eq cptd i , m i u, eq a i and cpe, tm I i , u I i uq cpe, tm I i , d I i uq 0. All costs associated with the two edges containing r in one of the copies G I are set to 0. For e tr 1 , r 2 u, where r 1 and r 2 are the roots of the two copies of G I , we set cpe, e I q 0 for each of the four edges e I incident to e.

The cost associated with any other pair of edges of G is equal to B 1; see Figure 4 for an illustration, where (some of) the reload costs are depicted (in blue), and a typical solution spanning tree of G is drawn with thicker edges.

We claim that the instance S of Partition is a Yes-instance if and only if G has a spanning tree with diameter at most B.

Assume first that S is a Yes-instance of Partition, and let S 1 , S 2 S be a solution.

We define a spanning tree T of G with diameter B as follows. We describe the subtree of T restricted to one of the copies of G I , say T I . The spanning tree T of G is defined by union of two symmetric copies of T I , one in each copy of G I , together with the edge tr 1 , r 2 u. Tree T I consists of the two edges tr, u 1 u, tr, d 1 u and two paths P u , P d (corresponding to the upper and the lower path, respectively defined as follows; see Figure 4). For i rn ¡ 1s, the path P u (resp. P d ) contains the edge tu I i , u i 1 u (resp. td I i , d i 1 u), and if a i S 1 we add the three edges tu i , m i u, tm i , m I i u, tm I i , u I i u to P u , and the edge td i , d I i u to P d . Otherwise, if a i S 2 , we add the edge tu i , u I i u to P u and the three edges td i , m i u, tm i , m I i u, tm

I i , d I i u to P d . Since °xS 1 x °xS 2 x B
2 , it can be easily checked that both paths P u and P d have diameter B 2 in each of the two copies of G I , and therefore T is a spanning tree of G with diameter B.

Conversely, let T be a spanning tree of G with diampT q ¤ B. Let G 1 , G 2 be the two copies of G I in G, and let r 1 , r 2 be their respective roots. Since the edge tr 1 , r 2 u is a bridge of G, it necessarily belongs to T . By the construction of G, the choice of the reload costs, and since diampT q ¤ B, it can be verified that, for j t1, 2u, T G j consists of two paths P j u , P j d intersecting at the root r i where P j u (resp. P j d ) contains all vertices u I i and u i 1 (resp. d I i and d i 1 ) of the corresponding copy of G I . This can be observed by the fact that given i 0 rns the subpath u i 0 m i 0 m I i 0 d I i 0 cannot be in T . First note that, i u) or by the edge tu i , u I i u (resp. td i , d I i u). Therefore, for j t1, 2u and x tu, du, it holds that d j x : diampP j x q °iI j x a i , where I j

as cptu I i 0 , m I i 0 u, td I i 0 , m I i 0 uq cptu I i 0 , u i 0 u, tu i 0 , m i 0 uq B 1 ¡ B, neither tu I i 0 , m I i 0 u nor tu I i 0 , u i 0 u is in T . As u I i 0 still
x is the set of indices i t1, . . . , nu such that the edge tm i , m I i u belongs to path P j

x . Note also that, for j t1, 2u, by construction we have that

d j u d j d °n i1 a i , implying in particular that maxtd j u , d j d u ¥ B 2 .
On the other hand, by the structure of T it holds that

B ¥ diampT q ¥ maxtd 1 u , d 1 d u maxtd 2 u , d 2 d u ¥ B 2 B 2 B. (1)
Equation ( 1) implies, in particular, that d

A polynomial-time algorithm for cactus graphs

In this section we present a polynomial-time algorithm for Diameter-Tree problem on cactus graphs. We begin with a definition of cactus graphs and an overview of their structure.

A biconnected component, or block, of a graph is a maximal biconnected induced subgraph of it. The block tree of a graph G is a tree whose nodes are the cut vertices and the blocks of G. Every cut vertex of G is adjacent in the block tree to all the blocks that contain it. The block tree of a graph is unique and can be computed in polynomial time [START_REF] Diestel | Graph Theory[END_REF]. A graph is a cactus graph if every block of it is either a cycle or a single edge. We term these blocks cycle blocks and edge blocks, respectively.

In this section, we present a polynomial-time algorithm that solves the decision version of the Diameter-Tree optimization problem, which we call Diameter-Tree*. Specifically, the input to the latter problem is an edge-colored graph G, a reload cost function c, and an integer k. The goal is to decide whether the input graph G has a spanning tree T with diampT q ¤ k. Observation 1. The Diameter-Tree problem can be solved in time Op|I| ¤ f p|I|qq if its decision version Diameter-Tree*can be solved in time f p|I|q, where |I| denotes the size of the instance.

Proof. Given an algorithm to decide Diameter-Tree*, one can perform a binary search over all the possible values for diampT q to determine the smallest value k for which the algorithm returns Yes. Since 0 ¤ diampT q |V pGq| ¤ max c, this requires at most logp|V pGq| ¤ max c log |V pGq| log max c Op|I|q invocations of the decision algorithm.

Our algorithm uses dynamic programming on the block tree of the input graph. We add a pendant vertex r to the input graph, so that its incident edge constitutes an edge block B r . We color this edge with a new color, such that the reload cost of this color and any other color is zero. Clearly, the obtained instance is equivalent to the original. The algorithm processes the block tree of G in a bottom-up manner starting from its leaves, proceeding towards B r while maintaining partial solutions for each block. At each step of the processing, it uses an algorithm that solves an instance of the 2-Sat problem as a subroutine. We proceed with definitions related to this structure.

We consider the block tree as a tree rooted at B r . For a block B of G, we denote by CpBq the set of blocks that are immediate descendants of B in the block tree and refer to them as the children of B. Similarly, the parent of a block B $ B r is the first block after B on the path from B to B r in the block tree. We denote by C E pBq and C C pBq the sets of edge blocks and cycle blocks of CpBq, respectively. We denote by G B the subgraph of G induced by the union of all (not necessarily proper) descendants of B. The anchor apBq of a block B $ B r is the cut vertex separating B from its parent, and apB r q r. Consult Figure 5 for the following definitions. Let B be a cycle block, and e an edge of B. Clearly, B ¡ e is a path P e that contains all the vertices of B and the graph G B ¡ e is connected. The vertex apBq divides P e into two subpaths that we denote by P e, and P e,¡ where the signs are chosen arbitrarily. Note that one of these subpaths is possibly trivial (i.e., it consists of one vertex, namely apBq). We divide G B into two induced subgraphs: subgraph G B,e, (resp. G B,e,¡ ) is induced by the vertices that are reachable from apBq without using edges from P e,¡ (resp. P e, ). Note that G B,e, and G B,e,¡ intersect exactly at apBq, and the degree of apBq is one in both subgraphs unless the subgraph under consideration is trivial. We denote by a pBq (resp. a ¡ pBq) the unique neighbor of apBq in G B,e, (resp. G B,e,¡ ). For D t , ¡u, we denote C e,D pBq tC CpBq | apCq P e,D u. We have G B,e,D P e, ¡ CC e,D pBq G C © . We define the set of graphs defined in this way by a block B as follows. We note that every H RpBq contains the vertex apBq which we denote as rpHq.

Furthermore, if H is not trivial rpHq has exactly one neighbor in H which we denote as rpHq. Note that rpHq ta pBq, a ¡ pBqu whenever H is not trivial. We use the same notations also for spanning subgraphs H I of H, i.e., rpH I q rpHq and rpH I q rpHq.

A spanning tree T of G is obtained from G by the removal of one edge from every cycle block of G. Let T be a spanning tree of G that does not contain the edge e of some cycle block B. The spanning tree T rG B s of G B is the union of two spanning trees: a tree T B,e, spanning G B,e, and a tree T B,e,¡ spanning G B,e,¡ that intersect exactly at apBq.

We proceed with definitions and results that relate the diameters and eccentricities of a spanning tree within a cycle block and its children. We denote by EpBq gpH, H I q pTrHsq pTrH I sq ¨,

where f, g, h are functions that depend only on e, e, and subgraphs of R e , but not on T .

Proof. Let P be a path of G and P 1 , . . . , P be subpaths of P such that P 1 and P contain one endpoint of P each, and every two consecutive subpaths P i , P i 1 , pi r ¡ 1sq have exactly one edge in common. Then cpP q ° i1 cpP i q. Let H R e , and consider a vertex v $ rpHq of H. We have dist T papBq, vq dist T papBq, rpHqq dist T rHs prpHq, vq. We note that dist T papBq, rpHqq does not depend on T but only on e, e, and H, i.e., it is a function f of H. Therefore, max vV pHq¡rpHq dist T papBq, vq f pHq pTrHsq max vV pTq¡V pP e,D q dist T papBq, vq max HR e,D pfpHq pTrHsqq.

Clearly, max vV pP e,D q dist T papBq, vq P e,D papBqq. Combining the last two lines, we obtain (2).

We proceed with the diameter of T . Let v 1 , v 2 be two vertices in distinct subgraphs

H 1 , H 1 R e . We have dist T pv 1 , v 2 q dist T prpH 1 q, rpH 2 qq dist T rH 1 s pv 1 , rpH 1 qq dist T rH 2 s pv 2 , rpH 2 qq
where the first term is a function g of H 1 and H 2 . We conclude similarly:

max v 1 H 1 ,v 2 H 2 dist T pv 1 , v 2 q gpH 1 , H 2 q pTrH 1 sq pTrH 2 sq.
Let v 1 be a vertex of P e,D and v 2 be a vertex of a subgraph H R e,D . We have

dist T pv 1 , v 2 q dist T pv 1 , rpHqq dist T rHs pv 2 , rpHqq max v 2 H dist T pv 1 , v 2 q dist T pv 1 , rpHqq pTrHsq max v 1 P e,D ,v 2 H dist T pv 1 , v 2 q ¢ max v 1 P e,D dist T pv 1 , rpHqq pTrHsq
where the first term is a function hpHq. Therefore,

max v 1 B,v 2 H dist T pv 1 , v 2 q hpHq pTrHsq.
Considering pairs of vertices from B and pairs of vertices that are in the same subgraph

H R e,D we conclude (3).

We proceed with the description of the algorithm. Our algorithm computes a set of "best" spanning trees for every block B. For a graph H RpBq of some block B, λpHq is a spanning tree T of H with diameter at most k that minimizes the eccentricity of rpHq (in T ). Formally, let S k pHq denote the set of spanning trees of H having diameter at most k. Then λpHq 4 u if S k pHq r arg min T S k pHq T prpHqq otherwise. For every block B and every graph H RpBq we compute λpG B q. If λpG B q u for some edge block B then G B (thus G as well) does not contain a spanning tree of diameter at most k. In this case the algorithm stops and returns No. If pλpG B,e, q uq pλpG B,e,¡ q uq diampλpG B,e, q λpG B,e,¡ qq ¡ k for every edge e of B of a cycle block B, then G B does not contain a spanning tree with diameter at most k and the algorithm returns No. Otherwise, the processing continues until finally B r is processed successfully and the algorithm returns Yes, since λpG Br q λpGq is a spanning tree of G with diameter at most k.

In the sequel we will mostly confine ourselves to cycle blocks, and overlook the case of edge block which is, by far, simpler. We first show the following lemma stating that the above strategy is valid, i.e., for every H RpBq, a valid value for λpHq can be computed from tλpH I q | H I RpCq, C CpBqu. We denote by ΛpHq the set of all spanning trees T of H that can be obtained from spanning trees λpH I q of the children of B. Formally, ΛpHq Clearly, diamp T rH I sq ¤ diamp T q ¤ k and similarly, diampP e,D q ¤ k. We define the following spanning tree of H.

Tλ P e,D ¤ ¥ ¤ H I R e,D
λpH I q

.

By definition, diampλpH I qq ¤ k and pλpH I qq ¤ p T pH I qq for every H I . Then, by Lemma 1, we have diamp Tλ q ¤ k and p Tλ q ¤ p T q, i.e., Tλ ΛpHq is a valid value for λpHq.

We now reduce the problem of computing λpHq to a decision problem. We define boolean functions λ as follows. For a block B and H RpBq the value λpH, iq is true if and only if there exists a spanning tree T of H such that diampT q ¤ k and pTq ¤ i. Observation 2. Diameter-Tree*can be decided in time |I| 2 ¤fp|I|q if λ can be computed in time f p|I|q where |I| denotes the size of the instance. Proof. Given an algorithm A that computes the function λ in time f p|I|q, we can obtain an algorithm that computes the function λ in time |I| ¤ f p|I|q as follows. Perform a binary search over the possible values of i (i.e., r0, ks) by invoking ApH, iq to find the smallest value of i for which A returns true. This requires at most log k invocations of A which is linear in the size of the input, as observed in Observation 1. Since the functions λ are computed once for every edge of G, the result follows.

In the rest of this section we present a polynomial-time algorithm for the following decision problem

Input: A graph H RpBq where B is a cycle block, a nonnegative integer i ¤ k, tλpH I q | H I RpCq, C CpBqu. Output: λpH, iq.
Let H G B,e,D for some edge e of B and D t , ¡u, We build an instance φ of 2-Sat over the following variables

2 x e I ,D | e I C, C C C pBq, D t , ¡u @ .
A subgraph F of H implies the following truth assignment to these variables: x e I ,D is true if and only if F contains the path P e I ,D . We denote by φpF q the truth value of φ resulting from such an assignment.

We first construct a formula φ 1 such that φ 1 pTq is true for any spanning tree T of H. Then we construct a formula φ 2 such that φ 2 pTq is true for a spanning tree T ΛpHq of H such that diampT q ¤ k, pTq ¤ i.

To finalize the proof, we will show that φ is satisfiable if and only if λpH, iq is true. We start with the construction of φ 1 . For two consecutive edges e 1 , e 2 of a cycle block C C C pBq, where e 1 is in P e 2 , (therefore, e 2 is in P e 1 ,¡ ). the formula φ 1 contains two clauses x e 2 , x e 1 ,¡ and x e 2 , x e 1 ,¡ . Every spanning tree T of H satisfies x e 2 , x e 1 ,¡ since otherwise T contains neither P e 2 , nor P e 1 ,¡ implying that the common vertex v of e 1 and e 2 is not reachable from apCq in T . Similarly T satisfies x e 2 , x e 1 ,¡ since otherwise T contains both P e 2 , and P e 1 ,¡ implying that v is reachable from apCq using two edge-disjoint paths.

We proceed with the construction of φ 2 . Let

T peq P e,D ¤ ¥ ¤ CpC E pBqC B,e,D q ¤ H I RpCq λpH I q ,
i.e., the tree obtained by the union of P e,D and all the trees λpH I q that intersect P e,D . Note that every tree spanning H contains T peq as a subtree. For H I G C,e I ,D I RpCq we denote by x H I the variable x e I ,D I that corresponds to H I . Also, we denote by P H I the path P e I ,D I, which is the intersection of H I with C. For every pair of graphs λpH I 1 q, λpH I 2 q of the input such that diampT peq λpH I 1 q λpH I 2 qq ¡ k or pT peq λpH I 1 q λpH I 2 qq ¡ i we add to φ 2 a clause x H I

1 x H I 2 .
The following observation is important for the rest of this section. Observation 3. Let H I , H P RpCq be such that H I is a subgraph H P . Then pλpH I qq ¤ pλpH P qq for any valid values of λpH I q and λpH P q. Lemma 3. If λpH, iq is true then φ is satisfiable.

Proof. By Lemma 2, ΛpHq contains a spanning tree T ¦ that is a valid value for λpHq.

Since λpH, iq is true, diampT ¦ q ¤ k and pT ¦ q ¤ i. We will show that φpT ¦ q is true. We have already observed that φ 1 pT ¦ q is true. It remains to show that φ 2 pT ¦ q is true.

Assume for a contradiction that a clause x H I 1 x H I 2 of φ 2 is not satisfied by T ¦ for some H I 1 RpC 1 q and some H I 2 RpC 2 q. By the construction of φ 2 , diampT peq λpH I 1 q λpH I 2 qq ¡ k or pT peq λpH I 1 qλpH I 2 qq ¡ i. Since the clause is not satisfied, both x H I 1 pT ¦ q and x H I 2 pT ¦ q are true. Therefore, T ¦ contains both P H I 1 and P H I 2 . For j t1, 2u, let P H P j be the longest path P e I ,C j that contains P H I j and contained in T ¦ . Then T ¦ contains both λpH P 1 q and λpH P 2 q. By Observation 3, we have pλpH P j qq ¥ pλpH P j qq for j t1, 2u. Then pT ¦ q ¥ pT peq λpH P 1 q λpH P 2 qq ¥ pT peq λpH I 1 q λpH I 2 qq. Furthermore, by Lemma 1, diampT ¦ q ¥ diampT peq λpH P 1 q λpH P 2 qq ¥ diampT peq λpH I 1 q λpH I 2 qq. We conclude that either diampT ¦ q ¡ k or pT ¦ q ¡ i, a contradiction. Indeed, otherwise either a child block C is contained in J, in which case every vertex of C is reachable from apCq using two vertex disjoint paths, or two edges of a cycle block C are not in J, in which case there is a vertex of C that is not reachable from apCq. In both cases φ 1 contains a falsified clause. Let e EpBq be the vector consisting of the edges not contained in J, and let

T ¦ T peq ¤ ¥ ¤ CCpBq pλpG C,e C , q λpG C,e C ,¡ qq .
Clearly, T ¦ ΛpG B,e,D q. It remains to show that diampT ¦ q ¤ k and pT ¦ q ¤ i. Assume that diampT ¦ q ¡ k. Then T ¦ contains a path P between two vertices of u, v with cpP q ¡ k. This path intersects at most two subgraphs λpH I 1 q and λpH I 2 q, i.e., P is a path of T peq λpH I 1 q λpH I 2 q. Therefore, diampT peq λpH I 1 q λpH I 2 qq ¡ k, implying that φ 2 contains the clause x H I

1 x H I 2 .
Since this φ 2 is satisfied, at least one of x H I 1 , x H I 2 , say x H I 1 ,is false in the assignment. Then J (therefore also T ¦ ) does not contain P H I 1 , contradicting the fact that T ¦ contains λpH I 1 q. Corollary 1. λpH, iq can be computed in time Opn 2 q where n is the number of vertices of G.

Proof. The number of variables in φ is at most twice the number of edges of G which is linear in the number of vertices of G. Therefore, the size of φ is Opn 2 q. Using Lemma 1, the diameters and eccentricities of the graphs can be computed in constant time from the diameters and eccentricities of their subgraphs. Therefore, every clause of φ can be generated in constant time. Finally, the satisfiability of φ can be checked in time linear to its size, i.e., Opn 2 q.

Combining the above corollary with Observations 1 and 2 we conclude Theorem 4. The Diameter-Tree problem can be solved in time Op|I| 5 q for cactus graphs where |I| is the size of the instance.

FPT algorithm parameterized by k tw ∆

In this section we prove that the Diameter-Tree problem is FPT on general graphs parameterized by k, tw, and ∆. The proof is based on standard, but nontrivial, dynamic programming on graphs of bounded treewidth. It should be mentioned that we can assume that a tree decomposition of the input graph G of width Optwq is given together with the input. Indeed, by using for instance the algorithm of Bodlaender et al. [START_REF] Bodlaender | A c k n 5-approximation algorithm for treewidth[END_REF], we can compute in time 2 Optwq ¤ n a tree decomposition of G of width at most 5tw. Note that this running time is clearly dominated by the running time stated in Theorem 5. Recall also that, as mentioned in Section 2, it is possible to transform in polynomial time a given tree decomposition to a nice triple pD, r, Gq such that D has the same width as the given tree decomposition.

Theorem 5. The Diameter-Tree problem can be solved in time k Op∆¤tw 2 q ¤ n Op1q . In particular, it is FPT parameterized by k tw ∆.

Proof. The general idea behind the following algorithm is, given a tree decomposition D pY, X tX t | t V pY quq of a graph G, to keep track, at each step t V pTq of the dynamic programming algorithm, of the solution tree, restricted to the already explored part of the graph, together with the distance function from vertices of V pG t q to vertices of X t in this solution. In order to reduce the size of the dynamic programming table, we compress the partial solution tree. This is the role of the reduce function that is defined below. In particular, we show that the obtained reduced forest has size linear in |X t |. The α function that will be introduced later keeps track of the mentioned distances.

After explaining these concepts, it remains to explain how the algorithm combines partial solutions in order to obtain the ones of the next step.

In order to provide a formal description of the dynamic programming, we need some more definitions. Given a graph G and a set S of its vertices, we say that S is good for G if S intersects every connected component of G. Let F be a forest and S be a set of vertices of F that is good for F . We define ReducepF, Sq as the forest F I that is obtained from F by repetitively applying the following operations to vertices that are not in N F rSs as long as this is possible:

1. removing a vertex of degree 1 and 2. dissolving a vertex of degree 2.

Suppose now that ReducepF, Sq F I . We define the associated reduce function ϕ : V pFq Ñ V pF I q EpF I q as follows. For every vertex z V pFq, we define K z to be the set of vertices x of V pF I q such that there exists a path in F from z to x that does not use any vertex of V pF I qztxu. Note that, if z V pF I q, then K z tzu, since for each x V pF I qztzu, the path from z to x contains z, which is an element of V pF I qztxu. If K z contains only one element x, then we define ϕpzq x, otherwise we define ϕpzq K z . To show that ϕ is well-defined, we claim that 1 ¤ |K z | ¤ 2 and if |K z | 2 then K z EpF I q. Indeed, since each connected component of F contains an element of S, we have |K z | ¥ 1.

Assume that K z contains two distinct vertices x 1 and x 2 . By definition, we know that x 1 and x 2 are in the same connected component of F and also of F I . Let P i be the path from z to x i , i t1, 2u, in F and let P be the path from x 1 to x 2 in F rV pP 1 q V pP 2 qs. By definition of x 1 and x 2 , V pPq V pF I q tx 1 , x 2 u. Moreover, since F is a forest, P is the unique x 1 x 2 -path in F . Let us assume that tx 1 , x 2 u is not an edge of F I and let

x 3 be a vertex of F I on the path from x 1 to x 2 in F I . Then x 3 should be in P . This contradicts the fact that V pPq V pF I q tx 1 , x 2 u. As F I is a forest, this also implies that |K z | ¤ 2. Intuitively, given z V pFq, either z V pF I q and so K z tzu, or z has been removed from the forest after the application of Operation 1 or Operation 2 and then K z corresponds to the vertex or edge we should start from if we want to recover z using the reverse operation of Operation 1 and Operation 2. Roughly speaking, a vertex z V pFq will be represented by a vertex or an edge of F I , depending on K z , thanks to the function ϕ. Note that a given vertex or edge in F I can represent 0, 1, or more vertices of F .

We now proceed with the dynamic programming algorithm that solves Diameter-Tree*, the decision version of Diameter-Tree. Let pG, χ, c, kq be an instance of Diameter-Tree*. Consider a nice triple pD, r, Gq where D is a tree decomposition D pY, X tX t | t V pY quq of G with width at most tw and G tG t | t V pY qu.

For each t V pY q we set w t |X t | and V t V pG t q. We also refer to the vertices of X t as t-terminals and to the edges that are incident to vertices in X t as t-terminal edges.

Given a forest F such that X t V pFq, we denote by X F t the set of all t-terminals and all non-t-terminal edges of F .

We provide a table R t that the dynamic programming algorithm computes for each node of D. For this, we need first the notion of a t-pair, that is a pair pF, αq where:

• F is a forest such that 1. X t is good for F , 2. X t V pFq, 3. N F pX t q N G pX t q, 4. |V pFqzN F rX t s| ¤ w t ¡ 2, and 5. |te EpF q | e X t ru| ¤ 2w t ¡ 3 and • α : X t ¢ X F t Ñ r0, ks tuu is such that αpv, aq $ u if and only if v and a are in the same connected component of F . We call the vertices in V pFqzN F rX t s external vertices of F and the edges of te EpF q | e X t ru external edges of F . Intuitively a t-pair pF, αq, corresponding to a partial solution, is such that there exists a spanning forest F of G t , such that F Reducep F , X t q and for each z V p F q and v X t , the cost to go from z to v in F is upper-bounded by αpv, K z q. The reason why we do not allow the edges incident to X t to be modified, by the reduce function, is because we will need them to compute the reload cost when we will consider the next bags.

We need the function β t : adj G pXtq 2 ¨Ñ r0, ks tuu so that, for each e 1 , e 2 adj G pX t q, if there exists x X t such that e 1 e 2 txu, then β t pe 1 , e 2 q cpe 1 , e 2 q, otherwise β t pe 1 , e 2 q u. Intuitively, the function β t takes the role of the reload cost function but is defined between edges incident to a given vertex of the working bag X t instead of being defined between colors. In particular, thanks to this, we do not have to take into consideration the number of colors.

Let pF, αq be a t-pair. Given a t-pair pF, αq as above we say that it is admissible if for every pa, a I q X F t ¢ X F t one of the following holds:

• there is no path between a and a I in F containing a vertex in X t ,

• one, say a, of a, a I is a vertex in X t and αpa, a I q ¤ k,

• some internal vertex b of the path P between a and a I in F belongs in X t and α t pb, aq β t pe ¡ , e q α t pb, a I q ¤ k, where e , e ¡ are the two edges in P that are incident to b.

Intuitively, the admissibility of a t-pair pF, αq assures that the transferring cost, indicated by α, between any two external elements is bounded by k.

We also need to explain how to combine t-pairs. Let pF 1 , α 1 q and pF 2 , α 2 q be two t-pairs where F 1 and F 2 are edge-disjoint and their union F is a forest. Let also β : adj F 1 pX t q ¢ adj F 2 pX t q Ñ r0, ks tuu. We define the function α 1 β α 2 : X t ¢ X F t Ñ r0, ks tuu that builds the transferring costs of moving in F by taking into account the corresponding transferring costs in F 1 and F 2 . The values of α 1 β α 2 are defined as follows. Let pv, aq X t ¢ X F t . Let P be the path in F between v and a and let V pPq tv 0 , . . . , v r u, ordered in the way these vertices appear in P and assuming that v 0 v. To simplify notation, we assume that tv 0 , v 1 u is an edge of F 1 (otherwise, exchange the roles of F 1 and F 2 ). Given i rr ¡ 1s, we define e ¡ i (resp. e i ) as the edge incident to v i that appears before (resp. after) v i when traversing P from v to a. We define the set of indices

I ti | e ¡
i and e i belong to different sets of tEpF 1 q, EpF 2 quu. Let I ti 1 , . . . , i q u, where numbers are ordered in increasing order and we also set i 0 0.

Then we set

α 1 β α 2 pv, aq ḩr0,t q¡1 2 us α 1 pv 2i h , v 2i h 1 q ḩr0,t q¡2 2 us α 2 pv 2i h 1 , v 2i h 2 q ḩrqs βpe ¡
i h , e i h q α pq mod 2q 1 pv iq , aq.

Roughly speaking, α 1 β α 2 pv, aq is the cost of the path P from v to a in F calculated as the sum of the cost of each connected component, provided by α 1 and α 2 , of P F 1 and P F 2 together with the sum of the costs, provided by β, of each transition from F 1 to F 2 and F 2 to F 1 used by P .

It is now time to give the precise definition of the table R t of our dynamic programming algorithm. A pair pF, αq belongs in R t if G contains a spanning tree T where diampT q ¤ k and the forest F T rV t s (i.e., the restriction of T to the part of the graph that has been processed so far) satisfies the following properties:

• Reducep F , X t q F , with the reduce function ϕ, • for each x X t and y X F t , αpx, yq u if and only if x and y are in two different connected components in F and if αpx, yq u, then for each z ϕ ¡1 pyq, cost F px, zq u and αpx, yq ¥ cost F px, zq. Notice that each pF, αq as above is a t-pair. Indeed, Conditions 1-3 follow by the fact that T is a spanning tree of G and therefore F is a spanning forest of G t . Conditions 4 and 5 follow by the fact that the number of internal vertices (resp. edges) of a tree with no vertices of degree two is at most two less than the number of leaves (resp. at most twice the number of leaves minus three). Moreover, the values of α are bounded by k because the diameter of T is at most k and therefore the same holds for all the connected components of F . Notice that, for the same reason, all pairs in R t must be admissible.

In the above definition, the external vertices and edges of F correspond to the parts of F that have been "compressed" during the reduction operation and the function α stores the transfer costs between those parts and the terminals. In this way, the trees in the t-pairs in R t "represent" the restriction of all possible solutions in G t . Moreover, the values of α indicate how these partial solutions interact with the t-terminals.

Our next concern is to bound the size of R t .

Claim 1. For every t V pY q, it holds that |R t | ¤ k Op∆¤tw 2 q ¤ p∆ ¤ twq Optwq . Proof. As we impose N rX t s V pFq, we have at most 2 ∆¤tw choices for the set te EpF q | e X t ru and at most p∆ ¤ twq Optwq choices for the other edges or vertices. So the number of forests we take into consideration in R t is at most 2 ∆¤tw ¤ p∆ ¤ twq Optwq . As the number of vertices and the number of edges of F is upper bounded by Op∆ ¤ twq, the number of functions α is at most k Op∆¤tw 2 q . So |R t | ¤ k Op∆¤tw 2 q ¤ p∆ ¤ twq Optwq and the claim holds.

Clearly, pG, χ, c, kq is a Yes-instance if and only if R r r. We now proceed with the description of how to compute the set R t for every node t T . For this, we will assume inductively that, for every descendant t I of t, the set R t I has already been computed. We distinguish several cases depending on the type of node t:

• If t is a leaf node. Then G t tr, ru and R t tppr, rq, ∅qu.

• If t is an vertex-introduce node. Let v be the insertion vertex of X t and let t I be the child of t. Then R t 2 pV pF I q tvu, EpF I qq, α ¨| hpF I , α I q R t I :

α α I 2 pv, vq, 0 ¨@ 2 pv, aq, u ¨| a X F I t ztvuqqs @ .
Notice that at this point v is just an isolated vertex of G t . This vertex is added in F and α is updated with the corresponding "void" transfer costs.

• If t is an edge-introduce node. Let e tx, yu be the insertion edge of X t and let t I be the child of t. We define F P pX t , teuq and we set up α P : X t ¢X F P t Ñ r0, ks tuu (notice that X F P t X t ) so that α P px, yq α P py, xq 0 and is u for all other pairs of X t ¢ X t . Then R t R t I tpF, αq | pF, αq is admissible, F is a forest, and there exists a pair pF I , α I q R t I such that F F I F P and α α I βt α P u.

In the above case, the single edge graph F P is defined and the F of each new t-pair is its union with F I . Similarly, the function α P encodes the trivial transfer costs in F P . Also, α is updated so that it includes the fusion of the transfer costs of α and α P .

• If t is an forget node. Let v be the forget vertex and let t I be the child of t. Then R t contains every t-pair pF, αq such that there exists pF I , α I q R t I where:

-if t is not the root of Y , then the connected component of F I containing v also contains another element v I X t (this is necessary as X t should always be good for F ), -F ReducepF I , X t q, with associated reduce function ϕ,

-we denote by Z the set of every edge and every vertex that is in F I but not in F . Moreover, if ϕpvq is a vertex, then we further set Z Ð Z tϕpvqu.

Notice also that if z Z, then ϕpzq ϕpvq. Then α α I | Xt¢pX F t ztϕpvquq 2 px, ϕpvqq, max yZ α I px, yq ¨| x X t @ . Notice that F is further reduced because v has been "forgotten" in X t . This may change the status of v as follows: either v is not any more in F or v is still in F but it is not a t-terminal. In the first case ϕpvq is either a vertex or an edge of F and in the second ϕpvq v. In any case we should update the values of αpx, φpvqq for every x X t to the maximum transition cost (with respect to α I ) from x to some element of Z.

• If t is an join node. Let t I and t P be the children of t. We define R t R t I tpF, αq | pF, αq is admissible, F is a forest, and there exist two pairs pF I , α I q R t I and pF P , α P q R t P such that F F I F P and α α I βt α P u.

The above case is very similar to the case of the edge-introduce node. The only difference is that now F P is now taken from R t P.

Taking into account Claim 1 on the bound of the size of R t , it is easy to verify that, in each of the above cases, R t can be computed in k Op∆¤tw 2 q ¤ p∆ ¤ twq Optwq steps. So we can solve our problem in time k Op∆¤tw 2 q ¤ p∆ ¤ twq Optwq ¤ n, and the theorem follows.

Polynomially bounded costs

So far, we have completely characterized the parameterized complexity of the Diameter-Tree problem for any combination of the three parameters k, tw, and ∆. In this section we focus on the special case when the maximum cost value is polynomially bounded by n. The following corollary is an immediate consequence of Theorem 5.

Corollary 2. If the maximum cost value is polynomially bounded by n, the Diameter-Tree problem is in XP parameterized by tw and ∆.

From Corollary 2, a natural question is whether the Diameter-Tree problem is FPT or Wr1s-hard parameterized by tw and ∆, in the case where the maximum cost value is polynomially bounded by n. The next theorem provides an answer to this question. Theorem 6. When the maximum cost value is polynomially bounded by n, the Diameter-Tree problem is Wr1s-hard parameterized by tw and ∆.

Proof. We present a parameterized reduction from the Bin Packing problem parameterized by the number of bins. In Bin Packing, we are given n integer item sizes a 1 , . . . , a n and an integer capacity B, and the objective is to partition the items into a minimum number of bins with capacity B. Jansen et al. [START_REF] Jansen | Bin packing with fixed number of bins revisited[END_REF] proved that Bin Packing is Wr1s-hard parameterized by the number of bins in the solution, even when all item sizes are bounded by a polynomial in the input size. Equivalently, this version of the problem corresponds to the case where the item sizes are given in unary encoding; this is why it is called Unary Bin Packing in [START_REF] Jansen | Bin packing with fixed number of bins revisited[END_REF].

Given an instance pta 1 , a 2 , . . . , a n u, B, kq of Unary Bin Packing, where k is the number of bins in the solution and where we can assume that k ¥ 2, we create an instance pG, χ, cq of Diameter-Tree as follows. The graph G contains a vertex r and, for i rns and j rks, we add to G vertices v i , i j , r i j and edges tr, 1 j u, tv i , i j u, tv i , r i j u, and t i j , r i j u. Finally, for i rn ¡ 1s and j rks, we add the edge tr i j , i 1 j u. Let G I be the graph constructed so far; see Figure 6 for an illustration. Similarly to the proof of Theorem 3, we define G to be the graph obtained by taking two disjoint copies of G I and identifying vertex r of both copies. Note that G can be clearly built in polynomial time, and that twpGq ¤ k 1 and ∆pGq 2k whether the reload costs are polynomial or not. Some questions still remain open. First of all, in the hardness result of Theorem 3, we already mentioned that the bound ∆ ¤ 3 is tight, but the bound tw ¤ 3 might be improved to tw ¤ 2. A relevant question is whether the problem admits polynomial kernels parameterized by k tw ∆ (recall that it is FPT by Theorem 5). Theorem 6 motivates the following question: when all reload costs are bounded by a constant, is the Diameter-Tree problem FPT parameterized by tw ∆? It also makes sense to consider the color-degree as a parameter (cf. [START_REF] Gözüpek | Constructing minimum changeover cost arborescenses in bounded treewidth graphs[END_REF]). Finally, we may consider other relevant width parameters, such as pathwidth (note that the hardness results of Theorems 1, 3, and 6 also hold for pathwidth), cliquewidth, treedepth, or tree-cutwidth.

v 2 v i v n r i 1 i 2 i k r i 1 r i 2 r i k 1 1 1 2 1 k 2 1 2 2 2 k n 1 n 2 n k r n 1 r n 2 r n k r 2 1 r 2 2 r 2 k r 1 1 r 1 2 r 1 k v 1

Figure 1 :

 1 Figure1: A transfer triple pF, R, αq where F is the depicted forest, R corresponds to the circled vertices, R F is the set of all vertices and edges except the dashed edges, and α is such that αpa, bq r0, ks and αpa, cq u.

3 rFigure 2 :

 32 Figure 2: Example of the graph G built in the reduction of Theorem 1.

RpBq 4 4 C 3 a(C 2 )Figure 5 :

 44325 Figure 5: The subgraph G B of a cactus G, defined by a cycle block B, and the two subgraphs defined by an edge e of B. The children of B are CpBq C e, pBq C e,¡ pBq, where C e, pBq tC 1 , C 2 , C 3 u and C e, pBq tC 4 , C 5 , C 6 u.

Lemma 2 .

 2 Let B be a cycle block and H RpBq, i.e., H G B,e,D for some edge e of B and some D t , ¡u. If λpHq $ u then ΛpHq contains a valid value for λpHq. Proof. Let T be a valid value for λpHq. Since T is a spanning tree of G B,e,D it does not contain the edge e. Moreover, it does not contain exactly one edge e C from every cycle block C C C pBq. Let e be the vector of these edges. Then T P e,D ¤ ¥ ¤ H I R e,D T rH I s .

Lemma 4 .

 4 If φ is satisfiable then λpH, iq is true. Proof. Consider the truth values of the variables x under an assignment that satisfies φ. Consider the graph J P e,D ¡ x e I ,D Itrue P e I ,D I © . Since φ 1 is satisfied by the assignment, J is a spanning tree of the graph of G B consisting of B and its child cycle blocks. In other words, J misses exactly one edge e C from each cycle bock C C C pBq.

Figure 6 :

 6 Figure 6: Graph G I built in the reduction of Theorem 6. Reload costs are not depicted.

Table

Table 1 :

 1 Summary of our results, where k, tw, ∆ denote the cost of the solution, the treewidth, and the maximum degree of the input graph, respectively. NPh stands for NP-hard. The symbol ' ' denotes that the result above still holds for polynomial costs.

	Problem	Parameterized complexity with parameter	Polynomial
		k tw	k ∆	tw ∆	k tw ∆	cases
		NPh for	NPh for	NPh for	FPT	in P on
	Diameter-Tree k 9, tw 2 k 0, ∆ 3 tw 3, ∆ 3 (Thm 5)	cacti
		(Thm 1)	(Thm 2)	(Thm 3)		(Thm ??)
	Diameter-Tree			XP (Thm 5)
	with poly costs			W[1]-hard
				(Thm 6)

  1 x °xS 2 x B Given an instance S ta 1 , a 2 , . . . , a n u of Partition, we create an instance pG, χ, cq of Diameter-Tree as follows. The graph G contains a vertex r, called the root, and for every integer a i where i rns, we add to G six vertices u i , u I We denote by H i the subgraph induced by these six vertices and seven edges. We add the edges tr, u 1 u, tr, d 1 u and, for i rn ¡ 1s, we add the edges tu I i , u i 1 u and td I

	B °xS x.	2 where

i , m i , m I i , d i , d I i and seven edges tu i , u I i u, tm i , m I i u, td i , d I i u, tu i , m i u, tu I i , m I i u, tm i , d i u, and tm I i , d I i u. i , d i 1 u. Let G I

  needs to be covered by T , this implies that there exists i ¡ i 0 such that in H i , T contains a path from d i to u i but by construction, this implies that T should contain both td i , m i u and tm i , u i u or both td i , d I i u and td I u and tu I i , u i u, three cases that imply the reload cost to be at least B 1. (resp. td i , m i u, tm i , m I

	tm I i , u I Furthermore, P j u (resp. P j	i , m I i u or both

i d ) contains the edge tu I i , u i 1 u (resp. td I i , d i 1 u) of the corresponding copy of G I , and the intersection of P j u (resp. P j d ) with the subgraph H i in the corresponding copy of G I is given by either the three edges tu i , m i u, tm i , m I i u, tm I i , u I i u i u, tm I i , d I

  EpBq defines the following set of non-trivial subgraphs of G B R e tG C | C C E pBqu tH GrC, e C , Ds | C C C pBq, D t , ¡u , |V pHq| ¡ 1u . Namely, this set contains one subgraph for every edge block in CpBq and two subgraphs for every cycle block in CpBq. Observe that R e CCpBq RpCq. We further partition the set R e of graphs into two sets R e, and R e, , according to the path that contains the root of the graph. Namely, R e,D tH R e | rpHq P e,D u, for D t , ¡u. the following lemma, for a spanning subgraph H of G B,e,D we use the shorthand pHq for H prpHqq. 1. Let B be a cycle block, e an edge of B, D t , ¡u, e CCpBq EpCq, and T a spanning tree of G B,e,D that does not contain the edges of e. Then

	In Lemma pTq max	¢	P e,D papBqq, max HR e,D	pfpHq pTrHsqq	,	(2)
	and diampT q is the maximum of the following four values:
	diampP e,D q,
	max HR e,D	diampHq,
	max HR e,D	phpHq pTrHsqq , and
	max H,H I R e,D

CC C pBq EpCq the set of vectors that contain one edge from each cycle block C C C pBq. A vector e

Acknowledgement. We would like to thank the anonymous reviewers for helpful comments that improved the presentation of the manuscript.

Work supported by the research program CNRS/TUBITAK grant no.114E731, TUBITAK 2221 programme, and by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).

(since we assume k ¥ 2q. Therefore, twpGq ∆pGq is indeed bounded by a function of k, as required. (Again, the claimed bound on the treewidth can be easily seen by building a path decomposition of G with consecutive bags of the form

Let us now define the coloring χ and the cost function c. Once more, for simplicity, we associate a distinct color with each edge of G, and thus it is enough to describe the cost function c for every pair of incident edges of G. The cost function is symmetric for both copies of G I , so we just focus on one copy. For i rns, let e 1 , e 2 be two distinct edges containing vertex v i . We set cpe 1 , e 2 q 2B 1 unless e 1 tv i , i j u and e 2 tv i , r i j u for some j rks, in which case we set cpe 1 , e 2 q a i . The cost associated with any other pair of edges of G is set to 0. Note that, as pta 1 , a 2 , . . . , a n u, B, kq is an instance of Unary Bin Packing, the reload costs of the instance pG, χ, cq of Diameter-Tree are polynomially bounded by |V pGq|.

We claim that pta 1 , a 2 , . . . , a n u, B, kq is a Yes-instance of Unary Bin Packing if and only if G has a spanning tree with diameter at most 2B.

Assume first that pta 1 , a 2 , . . . , a n u, B, kq is a Yes-instance of Unary Bin Packing, and let S 1 , . . . , S k be the k subsets of t1, . . . , nu defining the k bins in the solution. We define a spanning tree T of G with diampT q ¤ 2B as follows. For each of the two copies of G I , tree T contains, for i rn ¡ 1s and j rks, edges tr, 1 j u and tr i j , i 1 j u. For i rn ¡ 1s, if the item a i belongs to the set S j , we add to T the two edges tv i , i j u and tv i , r i j u; otherwise we add to T the edge t i j , r i j u. Since the total item size of each bin in the solution of Unary Bin Packing is at most B, it can be easily checked that T is a spanning tree of G with diampT q ¤ 2B.

Conversely, let T be a spanning tree of G with diampT q ¤ 2B, and we proceed to define a solution S 1 , . . . , S k of Unary Bin Packing. Let T 1 and T 2 be the restriction of T to the two copies of G I . By the choice of the reload costs and since diampT q ¤ 2B, for every i rns and every x t1, 2u, tree T x contains the two edges tv i , i j u and tv i , r i j u for some j rks, and none of the other edges incident with vertex v i . Therefore, for every x t1, 2u, tree T x consists of k paths sharing vertex r. This implies that diampT q ¥ 1 2 diampT 1 q 1 2 diampT 2 q, and since diampT q ¤ 2B, it follows that there exists x t1, 2u such that diampT x q ¤ B. Assume without loss of generality that x 1, i.e., that diampT 1 q ¤ B. We define the bins S 1 , . . . , S k as follows. For every i rns, if T 1 contains the two edges tv i , i j u and tv i , r i j u, we add item a i to the bin S j . Let us verify that this defines a solution of Unary Bin Packing. Indeed, assume for contradiction that for some j rks, the total item size in bin S j exceeds B. As bin S j corresponds to one of the k paths in tree T 1 , the diameter of this path would also exceed B, contradicting the fact that diampT 1 q ¤ B. The theorem follows.

Concluding remarks

We provided an accurate picture of the (parameterized) complexity of the Diameter-Tree problem for any combination of the parameters k, tw, and ∆, distinguishing