# Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter

Julien Baste, Didem Gözüpek, Ignasi Sau, Mordechai Shalom, Dimitrios M. Thilikos

► To cite this version:

Julien Baste, Didem Gözüpek, Ignasi Sau, Mordechai Shalom, Dimitrios M. Thilikos. Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter. IPEC 2017 - 12th International Symposium on Parameterized and Exact Computation, Sep 2017, Vienna, Austria. pp.3:1–3:12, 10.4230/LIPIcs.IPEC.2017.3 . hal-01733767

HAL Id: hal-01733767

https://hal.science/hal-01733767

Submitted on 16 Mar 2018

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter*†

Julien Baste¹, Didem Gözüpek², Christophe Paul³, Ignasi Sau⁴, Mordechai Shalom⁵, and Dimitrios M. Thilikos⁶

1 Université de Montpellier, LIRMM, Montpellier, France
baste@lirmm.fr

2 Department of Computer Engineering, Gebze Technical University, Kocaeli, Turkey

didem.gozupek@gtu.edu.tr

3 AlGCo project team, CNRS, LIRMM, France
paul@lirmm.fr

4 Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil and AlGCo project team, CNRS, LIRMM, France

sau@lirmm.fr

5 TelHai College, Upper Galilee, Israel and Department of Industrial Engineering, Boğaziçi University, Istanbul, Turkey
cmshalom@telhai.ac.il

6 Department of Mathematics, National and Kapodistrian University of Athens, Greece and AlGCo project team, CNRS, LIRMM, France

sedthilk@thilikos.info

## Abstract

We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph $G$, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of $G$ of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree $\Delta$ of the input graph. We prove that DIAMETER-TREE is para-NP-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with $\Delta = 3$, and Galbiati (2008) proved that it is NP-hard if $\Delta = 4$. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if $\Delta = 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 $\Delta$.

**1998 ACM Subject Classification** F.2.2 Nonnumerical Algorithms and Problems, C.2.1 Network Architecture and Design, G.2.2 Graph Theory

<figure><img src="image_2.png" /></figure>

<footnote>* This work has been supported by the bilateral research program of CNRS and TUBITAK under grant no.114E731, PASTA project of Université de Montpellier, TUBITAK 2221 programme, and by project DEMOGRAPH (ANR-16-CE40-0028).</footnote>

<footnote>† A full version of this article is permanently available at https://arxiv.org/abs/1703.01686.</footnote>
**Keywords and phrases** reload cost problems, minimum diameter spanning tree, parameterized complexity, FPT algorithm, treewidth, dynamic programming

Digital Object Identifier 10.4230/LIPIcs.IPEC.2017.3

1 Introduction

Numerous network optimization problems can be modeled by edge-colored graphs. Wirth and Steffan introduced in [28] 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 [9], 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 requires 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 [3, 19, 4, 5, 11, 1, 26]) 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 [6, 8].

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 [12]. 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 [12].

Recent works in the literature focused on numerous problems related to the reload cost concept: the minimum reload cost cycle cover problem [14], the problems of finding a path, trail or walk with minimum total reload cost between two given vertices [17], the problem of finding a spanning tree that minimizes the sum of reload costs of all paths between all pairs of vertices [15], various path, tour, and flow problems related to reload costs [2], the minimum changeover cost arborescence problem [13, 22, 20, 18], and problems related to finding a proper edge coloring of the graph so that the total reload cost is minimized [21].
The work in [28], 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 = (V, E)$ with a (non necessarily proper) edge-coloring $\chi : E(G) \to X$ and a reload cost function $c : X^2 \to \mathbb{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 availabilities 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 [28] 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 [12] 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 $\Delta$ (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 [24]. 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 [25]. 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 Table 1.

We first prove, by a reduction from 3-SAT, that DIAMETER-TREE is NP-hard on outer-planar 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 [28]. 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
3:4 Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter

<table><caption>■ Table 1 Summary of our results, where $k$, $tw$, $\Delta$ 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.</caption><thead><tr><th rowspan="2">Problem</th><th colspan="4">Parameterized complexity with parameter</th><th rowspan="2">Polynomial cases</th></tr><tr><th>k + tw</th><th>k + Δ</th><th>tw + Δ</th><th>k + tw + Δ</th></tr></thead><tbody><tr><td>DIAMETER-TREE</td><td>NPh for<br>k = 9, tw = 2<br>(Thm 1)</td><td>NPh for<br>k = 0, Δ = 3<br>(Thm 2)</td><td>NPh for<br>tw = 3, Δ = 3<br>(Thm 4)</td><td>FPT<br>(Thm 7)</td><td>in P on<br>cacti<br>(Thm 6)</td></tr><tr><td>DIAMETER-TREE<br>with poly costs</td><td>✓</td><td>✓</td><td>XP (Thm 7)<br>W[1]-hard<br>(Thm 9)</td><td>✓</td><td>✓</td></tr></tbody></table>

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 $\Delta \le 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 $\Delta \le 3$ in the general case where the triangle inequality is not necessarily satisfied, which had been left open in previous work [28, 12]. Note that $\Delta \le 3$ is best possible, as DIAMETER-TREE can be easily solved on graphs with $\Delta \le 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 \le 3$ and $\Delta \le 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 $\Delta$. 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 + \Delta$ is from PARTITION, which is a typical example of a weakly NP-complete problem [16], a natural question is whether DIAMETER-TREE, with parameter $tw + \Delta$, is para-NP-hard, XP, W[1]-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[1]-hard parameterized by $tw + \Delta$. The W[1]-hardness reduction is from the UNARY BIN PACKING problem parameterized by the number of bins, proved to be W[1]-hard by Jansen et al. [23].

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

**Further research.** In the hardness result of Theorem 4, the bound $\Delta \le 3$ is tight, but the bound $tw \le 3$ might be improved to $tw \le 2$. A relevant question is whether the problem admits polynomial kernels parameterized by $k + tw + \Delta$ (recall that it is FPT by Theorem 7). Theorem 9 motivates the following question: when all reload costs are bounded by a constant, is the DIAMETER-TREE problem FPT parameterized by $tw + \Delta$? It also makes sense to consider the *color-degree* as a parameter (cf. [20]). Finally, we may consider other relevant width parameters, such as pathwidth (note that the hardness results of Theorems 1, 4, and 9 also hold for pathwidth), cliquewidth, treedepth, or tree-cutwidth.
**Organization of the paper.** We start in Section 2 with some preliminaries about the DIAMETER-TREE problem. Basic definitions about graphs, parameterized complexity, and tree decompositions can be found in the full version. In Section 3 we provide the para-NP-hardness results, and in Section 4 we present the polynomial-time algorithm on cactus graphs and the FPT algorithm on general graphs parameterized by $k + \text{tw} + \Delta$. In Section 5 we focus on the case where the reload costs are polynomially bounded. Due to lack of space, the proof of the results marked with '[★]' can be found in the full version.

## 2 Reload costs and definition of the problem

For reload costs, we follow the notation and terminology defined by [28]. We consider edge-colored graphs $G = (V, E)$, where the colors are taken from a finite set $X$ and the coloring function is $\chi: E(G) \to X$. The reload costs are given by a nonnegative function $c: X^2 \to \mathbb{N}_0$, which we assume for simplicity to be symmetric. The cost of traversing two incident edges $e_1, e_2$ is $c(e_1, e_2) := c(\chi(e_1), \chi(e_2))$. By definition, reload costs at the endpoints of a path equal zero. Consequently, the reload cost of a path with one edge also equals zero. The reload cost of a path $P$ of length $\ell \ge 2$ with edges $e_1, e_2, \dots, e_\ell$ is defined as $c(P) := \sum_{i=2}^\ell c(e_{i-1}, e_i)$. The induced reload cost distance function is given by $\text{dist}_G^c(u, v) = \min\{c(P) \mid P \text{ is a path from } u \text{ to } v \text{ in } G\}$. The diameter of a tree $T$ is $\text{diam}(T) := \max_{u,v \in V} \text{dist}_T^c(u, v)$, where for notational convenience we assume that the edge-coloring function $\chi$ and the reload cost function $c$ are clear from the context.

The problem we study in this paper can be formally defined as follows:

**MINIMUM RELOAD COST DIAMETER SPANNING TREE (DIAMETER-TREE)**

**Input:** A graph $G = (V, E)$ with an edge-coloring $\chi$ and a reload cost function $c$.

**Output:** A spanning tree $T$ of $G$ minimizing $\text{diam}(T)$.

If for every three distinct edges $e_1, e_2, e_3$ of $G$ incident to the same node, it holds that $c(e_1, e_3) \le c(e_1, e_2) + c(e_2, e_3)$, we say that the reload cost function $c$ satisfies the *triangle inequality*. This assumption is sometimes used in practical applications [28].

Throughout the paper, we let $n$, $\Delta$, and $\text{tw}$ denote 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 also let $k$ denote the desired cost of a solution.

## 3 Para-NP-hardness results

We start with the para-NP-hardness result with parameter $k + \text{tw}$.

**► Theorem 1.** The DIAMETER-TREE problem is NP-hard on outerplanar graphs with only one vertex of degree greater 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 parameterized by $\text{tw}$ and $k$.

**Proof.** We present a simple reduction from 3-SAT. Given a formula $\varphi$ with $n$ variables and $m$ clauses, we create an instance $(G, \chi, c)$ of DIAMETER-TREE as follows. We may assume that there is no clause in $\varphi$ that contains a literal and its negation. The graph $G$ contains a distinguished vertex $r$ and, for each clause $c_j = (\ell_1 \lor \ell_2 \lor \ell_3)$, we add a clause gadget $C_j$ consisting of three vertices $v_{\ell_1}^j, v_{\ell_2}^j, v_{\ell_3}^j$ and five edges $\{r, v_{\ell_1}^j\}, \{r, v_{\ell_2}^j\}, \{r, v_{\ell_3}^j\}, \{v_{\ell_1}^j, v_{\ell_2}^j\},$ and $\{v_{\ell_2}^j, v_{\ell_3}^j\}$. This completes the construction of $G$. Note that $G$ does not depend on the
<figure><img src="image_3.png" /><figcaption>Figure 1 Example of the graph G built in the reduction of Theorem 1.</figcaption></figure>

formula $\varphi$ except for the number of clause gadgets, and that it is an outerplanar graph with only one vertex of degree greater than 3; see Figure 1 for an illustration.

Let us now define the coloring $\chi$ 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 will use just three different costs: 1, 5 and 10. We set

$$c(e_1, e_2) = \begin{cases} 10 & \text{if } e_1 = \{r, v_{\ell_{i_1}}^{j_1}\}, e_2 = \{r, v_{\ell_{i_2}}^{j_2}\} \text{ and } \ell_{i_1} = \overline{\ell_{i_2}}, \\ 5 & \text{if } e_1 = \{r, v_{\ell_{i_1}}^{j_1}\}, e_2 = \{r, v_{\ell_{i_2}}^{j_2}\} \text{ and } \ell_{i_1} \neq \overline{\ell_{i_2}}, \text{ and} \\ 1 & \text{otherwise.} \end{cases}$$

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 $\varphi$ 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 associated with a path from $r$ to a leaf of this tree is always 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$.

Assume first that $\varphi$ is satisfiable, fix a satisfying assignment $\psi$ of $\varphi$, and let us construct a spanning tree $T$ of $G$ with diameter at most 9. For each clause $c_j$, the tree $T^j$ is the tree spanning $C_j$ and containing the edge between $r$ and an arbitrarily chosen literal of $c_j$ that is set to true by $\psi$. $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, it holds that $\text{diam}(T) \le 9$.

Conversely, let $T$ be a spanning tree of $G$ with $\text{diam}(T) \le 9$. Then, the reload cost incurred at $r$ by any path traversing it is at most 5 since otherwise $\text{diam}(T) \ge 10$. For every $j \in [m]$, let $T_j$ be the subtree of $T$ induced by $C_j$ and let $\{r, v_{\ell_{ij}}^j\}$ 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 $\ell_{i_{j_1}} \neq \overline{\ell_{i_{j_2}}}$, since otherwise a path using these two edges would incur a cost of 10 at $r$. The variable in the literal $\ell_{ij}$ is set by $\psi$ so that $\ell_{ij}$ is true. All the other variables are set to an arbitrary value by $\psi$. Note that $\psi$ is well-defined, since we never encounter a literal and its negation during the assignment process. It follows that $\psi$ is a satisfying assignment of $\varphi$. $\blacksquare$

We proceed with the para-NP-hardness result with parameter $k + \Delta$.
**► Theorem 2.** The DIAMETER-TREE problem is NP-hard on graphs with $\Delta \le 3$, even with two different costs, $k = 0$, and a bounded number of colors. In particular, it is para-NP-hard parameterized by $k$ and $\Delta$.

**Proof.** We present a reduction from the restriction of 3-SAT to formulas where each variable occurs in at most three clauses; this problem was proved to be NP-complete by Tovey [27]. 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 [27].

We may assume that each variable occurs at least once positively and at least once negatively, as otherwise we may set such a variable $x$ to the value that satisfies all clauses in which it appears, and delete $x$ together with those clauses from the formula. We may also assume that each variable occurs exactly three times in the given formula $\varphi$. Indeed, let $x$ be a variable occurring exactly two times in the formula. We create a new variable $y$ and we add to $\varphi$ two clauses ($x \lor y$) and ($y \lor \bar{y}$). Let $\varphi'$ be the new formula. Clearly $\varphi$ and $\varphi'$ are equivalent, and both $x$ and $y$ occur three times in $\varphi'$. Applying these operations exhaustively clearly results in an equivalent formula where each variable occurs exactly three times. Summarizing, we may assume the following property:

⊲ Each variable occurs exactly three times in the given formula $\varphi$ of 3-SAT. Moreover, each variable occurs at least once positively and at least once negatively in $\varphi$.

Given a formula $\varphi$ with $n$ variables and $m$ clauses, we create an instance $(G, \chi, c)$ of DIAMETER-TREE with $\Delta(G) \le 3$ as follows. Let the variables in $\varphi$ be $x_1, \dots, x_n$. For every $i \in [n]$, we add to $G$ a variable gadget consisting of five vertices $u_i, v_i, p_i, r_i, n_i$ and five edges $\{u_i, v_i\}, \{v_i, p_i\}, \{p_i, r_i\}, \{r_i, n_i\},$ and $\{n_i, v_i\}$. For every $i \in [n-1]$, we add the edge $\{u_i, u_{i+1}\}$. For every $j \in [m]$, the clause gadget in $G$ consists of a single vertex $c_j$. We now proceed to explain how we connect the variable and the clause gadgets. For each variable $x_i$, we connect vertex $p_i$ (resp. $n_i$) to one of the vertices corresponding to a clause of $\varphi$ in which $x_i$ appears positively (resp. negatively). Finally, we connect vertex $r_i$ to the remaining clause in which $x_i$ appears (positively or negatively). Note that these connections are well-defined because of property ⊲. This completes the construction of $G$, and note that it indeed holds that $\Delta(G) \le 3$; see Figure 2(a) for an example of the construction of $G$ for a specific satisfiable formula $\varphi$ with $n=4$ and $m=5$.

Let us now define the coloring $\chi$ and the cost function $c$. We use nine colors $1, 2, \dots, 9$ associated with the edges of $G$ as follows. For $i \in [n]$, we set $\chi(\{p_i, r_i\}) = 1$ and $\chi(\{r_i, n_i\}) = 2$, and all edges incident to $u_i$ or $v_i$ have color 3. Finally, for $j \in [m]$, we color the edges containing $c_j$ with colors in $\{4, 5, 6, 7, 8, 9\}$, so that incident edges get different colors, and edges corresponding to positive (resp. negative) occurrences get colors in $\{4, 5, 6\}$ (resp. $\{7, 8, 9\}$); note that such a coloring always exists as each clause contains at most three variables; see Figure 2(b). We will use only two costs, namely 0 and 1, and recall that we consider only symmetric cost functions. We set $c(1, 2) = 1$, $c(1, i) = 1$ for every $i \in \{4, 5, 6\}$, $c(2, i) = 1$ for every $i \in \{7, 8, 9\}$, and $c(i, j) = 1$ for every distinct $4 \le i, j \le 9$. All other costs are set to 0. The following claim concludes the proof.

**► Claim 3.** [⊲] $\varphi$ is satisfiable if and only if $G$ contains a spanning tree with diameter 0. ◀

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 \in [n]$, and recall that this is unavoidable since otherwise the problem would be polynomial [28].

Finally, we present the para-NP-hardness result with parameter $tw + \Delta$.

**► Theorem 4.** The DIAMETER-TREE problem is NP-hard on planar graphs with $tw \le 3$ and $\Delta \le 3$. In particular, it is para-NP-hard parameterized by $tw$ and $\Delta$.
<figure><img src="image_4.png" /><figcaption>■ **Figure 2** (a) Graph $G$ described in the reduction of Theorem 2 for the formula $\varphi = (x_1 \lor \bar{x}_2 \lor x_3) \land (\bar{x}_1 \lor \bar{x}_4) \land (\bar{x}_3 \lor \bar{x}_4) \land (\bar{x}_1 \lor x_2 \lor x_3) \land (x_2 \lor x_4)$. The vertices $p_i, r_i, n_i$ corresponding to positive (resp. negative) occurrences are depicted with circles (resp. squares). An assignment satisfying $\varphi$ 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$ are depicted in blue.</figcaption></figure>

**Proof.** We present a reduction from the PARTITION problem, which is a typical example of a weakly NP-complete problem [16]. An instance of PARTITION is a multiset $S = \{a_1, a_2, \dots, a_n\}$ 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 $\sum_{x \in S_1} x = \sum_{x \in S_2} x = \frac{B}{2}$ where $B = \sum_{x \in S} x$.

Given an instance $S = \{a_1, a_2, \dots, a_n\}$ of PARTITION, we create an instance $(G, \chi, c)$ of DIAMETER-TREE as follows. The graph $G$ contains a vertex $r$, called the root, and for every integer $a_i$ where $i \in [n]$, we add to $G$ six vertices $u_i, u'_i, m_i, m'_i, d_i, d'_i$ and seven edges $\{u_i, u'_i\}, \{m_i, m'_i\}, \{d_i, d'_i\}, \{u_i, m_i\}, \{u'_i, m'_i\}, \{m_i, d_i\}$, and $\{m'_i, d'_i\}$. We denote by $H_i$ the subgraph induced by these six vertices and seven edges. We add the edges $\{r, u_1\}, \{r, d_1\}$ and, for $i \in [n-1]$, we add the edges $\{u'_i, u_{i+1}\}$ and $\{d'_i, d_{i+1}\}$. Let $G'$ be the graph constructed so far. We then define $G$ to be the graph obtained from two disjoint copies of $G'$ by adding an edge between both roots. Note that $G$ is a planar graph with $\Delta(G) = 3$ and $\text{tw}(G) = 3$. (The claimed bound on the treewidth can be easily seen by building a path decomposition of $G$ with consecutive bags of the form $\{u'_{i-1}, d'_{i-1}, u_i, d_i\}, \{u_i, d_i, m_i, u'_i\}, \{d_i, m_i, u'_i, m'_i\}, \{d_i, u'_i, m'_i, d'_i\}, \dots$)

Let us now define the coloring $\chi$ 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'$, and the same costs apply to the other copy. For every edge $e$ being either $\{u'_i, u_{i+1}\}$ or $\{d'_i, d_{i+1}\}$, for $1 \le i \le n-1$, we set $c(e, e') = 0$ for each of the four edges $e'$ incident with $e$. For every edge $e = \{m_i, m'_i\}$, for $1 \le i \le n$, we set $c(\{u_i, m_i\}, e) = c(\{d_i, m_i\}, e) = a_i$ and $c(e, \{m'_i, u'_i\}) = c(e, \{m'_i, d'_i\}) = 0$. All costs associated with the two edges containing $r$ in one of the copies $G'$ are set to 0. For $e = \{r_1, r_2\}$, where $r_1$ and $r_2$ are the roots of the two copies of $G'$, we set $c(e, e') = 0$ for each of the four edges $e'$ incident to $e$. The cost associated with any other pair of edges of $G$ is equal to $B+1$; see Figure 3 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. The following claim concludes the proof.

**Claim 5.** [★] The instance $S$ of PARTITION is a YES-instance if and only if $G$ has a spanning tree with diameter at most $B$. ▴
<figure><img src="image_5.png" /><figcaption>Figure 3 Graph *G* built in the reduction of Theorem 4, 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.</figcaption></figure>

4 Polynomial and FPT algorithms

We start this section by presenting the polynomial-time algorithm to solve the DIAMETER-
TREE problem on cactus graphs, equivalently called *cacti*. We first need some definitions.

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 *T* whose nodes are the cut vertices and the blocks of *G*. Every cut vertex is adjacent in *T* to all the blocks that contain it. Two blocks share at most one vertex. The block tree of a graph is unique and can be computed in polynomial time [10]. 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. It is well-known that cacti have treewidth at most 2. Given a forest *F* and two vertices *x* and *y*, we define *cost*<sub>*F*</sub>(*x*, *y*) to be *dist*<sub>*T*</sub><sup>*c*</sup>(*x*, *y*) if *x* and *y* are in the same tree *T* of *F* and where *c* is the given reload cost function, and ⊥ otherwise. Given a tree *T* and a vertex *v* ∈ *V*(*T*), we define the *eccentricity* of *v* in *T* to be max<sub>*v'*∈*V*(*T*)</sub> *cost*<sub>*T*</sub>(*v*, *v'*).

We present a polynomial-time algorithm that solves the decision version of the problem, which we call DIAMETER-TREE*: the input is an edge-colored graph *G* and an integer *k*, and the objective is to decide whether the input graph *G* has a spanning tree with reload cost diameter at most *k*. The algorithm to solve DIAMETER-TREE* uses dynamic programming on the block tree of the input graph.

As we aim at a *strongly* polynomial-time algorithm to solve DIAMETER-TREE, we *cannot* afford to solve the decision version for all values of *k*. To overcome this problem, we perform a double *binary search* on the possible solution values and two appropriate eccentricities, resulting (skipping many technical details) in an extra factor of (log *opt*)<sup>2</sup> in the running time of the algorithm, where *opt* is the diameter of a minimum cost spanning tree. This yields a polynomial-time algorithm solving DIAMETER-TREE in cactus graphs.

Roughly speaking, the algorithm first fixes an arbitrary non-cut vertex *r* of *G* and the block *B*<sub>*r*</sub> that contains it. Then it processes the block tree of *G* in a bottom-up manner starting from its leaves, proceeding towards *B*<sub>*r*</sub> 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. The intuition behind the instances of 2-SAT created by the algorithm is the following.

Suppose that we are dealing with a cycle block *B* of the block tree of *G* (the case of an edge block being easier). Note that any spanning tree of *G* contains all edges of *B* except one. Let *G*<sub>*B*</sub> be the graph processed so far (including *B*). For each potential partial solution *Q* in *G*<sub>*B*</sub>, we associate, with each edge *e* of *B*, a variable that indicates that *e* is the non-picked edge by the solution in *B*. Now, for any two such variables corresponding to intersecting blocks, we add to the formula of 2-SAT essentially two types of clauses: the first set of
3:10 Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter

clauses, namely $\phi_1$, guarantees that the non-picked edges (corresponding to the variables set to true in the eventual assignment) indeed define a spanning tree of $G_B$, while the second one, namely $\phi_2$, forces this solution to have diameter and eccentricity not exceeding the given budget $k$. The fact that $G$ is a cactus allows to prove that these constraints containing only two variables are enough to compute an optimal solution in $G_B$. Full details can be found in the full version.

► **Theorem 6.** [★] The DIAMETER-TREE problem can be solved in polynomial time on cacti.

In the following theorem we prove that the DIAMETER-TREE problem is FPT on general graphs parameterized by $k$, tw, and $\Delta$. 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 $\mathcal{O}(\mathrm{tw})$ is given together with the input. Indeed, by using for instance the algorithm of Bodlaender et al. [7], we can compute in time $2^{\mathcal{O}(\mathrm{tw})} \cdot 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 7.

► **Theorem 7.** [★] The DIAMETER-TREE problem can be solved in time $(k^{\Delta \cdot \mathrm{tw}} \cdot \Delta \cdot \mathrm{tw})^{\mathcal{O}(\mathrm{tw})} \cdot n^{\mathcal{O}(1)}$. In particular, it is FPT parameterized by $k$, tw, and $\Delta$.

5 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 $\Delta$. 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 7.

► **Corollary 8.** If the maximum cost value is polynomially bounded by $n$, the DIAMETER-TREE problem is in XP parameterized by tw and $\Delta$.

From Corollary 8, a natural question is whether the DIAMETER-TREE problem is FPT or W[1]-hard parameterized by tw and $\Delta$, in the case where the maximum cost value is polynomially bounded by $n$. The next theorem provides an answer to this question.

► **Theorem 9.** When the maximum cost value is polynomially bounded by $n$, the DIAMETER-TREE problem is W[1]-hard parameterized by tw and $\Delta$.

**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, \dots, 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. [23] proved that BIN PACKING is W[1]-hard parameterized by the number of bins in the solution, even when all item sizes are bounded by a polynomial of 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 [23].

Given an instance $((\{a_1, a_2, \dots, a_n\}, B, k))$ of UNARY BIN PACKING, where $k$ is the number of bins in the solution and where we can assume that $k \ge 2$, we create an instance $(G, \chi, c)$ of DIAMETER-TREE as follows. The graph $G$ contains a vertex $r$ and, for $i \in [n]$ and $j \in [k]$, we add to $G$ vertices $v_i, \ell_j^i, r_j^i$ and edges $\{r, \ell_j^1\}, \{v_i, \ell_j^i\}, \{v_i, r_j^i\}, \text{ and } \{\ell_j^i, r_j^i\}$. Finally, for $i \in [n-1]$ and $j \in [k]$, we add the edge $\{r_j^i, \ell_j^{i+1}\}$. Let $G'$ be the graph constructed so far; see Figure 4 for an illustration.

Similarly to the proof of Theorem 4, we define $G$ to be the graph obtained by taking two disjoint copies of $G'$ and identifying vertex $r$ of both copies. Note that $G$ can be clearly built in
<figure><img src="image_6.png" /><figcaption>Figure 4 Graph $G'$ built in the reduction of Theorem 9. The reload costs are not depicted.</figcaption></figure>

polynomial time, and that $\text{tw}(G) \le k+1$ and $\Delta(G) = 2k$ (since we assume $k \ge 2$). Therefore, $\text{tw}(G)+\Delta(G)$ 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 $\{v_i, \ell_1^i, \ell_2^i, \dots, \ell_k^i, r_1^i\}, \{v_i, \ell_1^i, \ell_2^i, \dots, \ell_{k-1}^i, r_1^i, r_2^i\}, \{v_i, \ell_1^i, \ell_2^i, \dots, \ell_{k-2}^i, r_1^i, r_2^i, r_3^i\}, \dots$)

Let us now define the coloring $\chi$ 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'$, so we just focus on one copy. For $i \in [n]$, let $e_1, e_2$ be two distinct edges containing vertex $v_i$. We set $c(e_1, e_2) = 2B + 1$ unless $e_1 = \{v_i, \ell_i^j\}$ and $e_2 = \{v_i, r_j^i\}$ for some $j \in [k]$, in which case we set $c(e_1, e_2) = a_i$. The cost associated with any other pair of edges of $G$ is set to 0. Note that, as $(\{a_1, a_2, \dots, a_n\}, B, k)$ is an instance of **UNARY BIN PACKING**, the reload costs of the instance $(G, \chi, c)$ of **DIAMETER-TREE** are polynomially bounded by $|V(G)|$. Again, the following claim concludes the proof.

**Claim 10.** $[+]$ $(\{a_1, a_2, \dots, a_n\}, B, k)$ is a YES-instance of **UNARY BIN PACKING** if and only if $G$ has a spanning tree with diameter at most $2B$. ▼

References

1. Satyam Agarwal and Swades De. Dynamic spectrum access for energy-constrained cr: single channel versus switched multichannel. *IET Communications*, 10(7):761–769, 2016.

2. E. Amaldi, Giulia Galbiati, and Francesco Maffioli. On minimum reload cost paths, tours, and flows. *Networks*, 57(3):254–260, 2011.

3. Stamatios Arkoulis, Evangelos Anifantis, Vasileios Karyotis, Symeon Papavassiliou, and Nikolaos Mitrou. On the optimal, fair and channel-aware cognitive radio network reconfiguration. *Computer Networks*, 57(8):1739–1757, 2013.

4. Suzan Bayhan and Fatih Alagoz. Scheduling in centralized cognitive radio networks for energy efficiency. *IEEE Transactions on Vehicular Technology*, 62(2):582–595, 2013.

5. Suzan Bayhan, Salim Eryigit, Fatih Alagoz, and Tuna Tugcu. Low complexity uplink schedulers for energy-efficient cognitive radio networks. *IEEE Wireless Communications Letters*, 2(3):363–366, 2013.

6. Aruna Prem Bianzino, Claude Chaudet, Dario Rossi, and Jean-Louis Rougier. A survey of green networking research. *IEEE Communications Surveys & Tutorials*, 14(1):3–20, 2012.

7. Hans L. Bodlaender, Pral Grønras Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A $c^k n$ 5-approximation algorithm for treewidth. *SIAM Journal on Computing*, 45(2):317–378, 2016.

8. Abdulkadir Celik and Ahmed E Kamal. Green cooperative spectrum sensing and scheduling in heterogeneous cognitive radio networks. *IEEE Transactions on Cognitive Communications and Networking*, 2(3):238–248, 2016.

9. Claude Desset, Noman Ahmed, and Antoine Dejonghe. Energy savings for wireless terminals through smart vertical handover. In *Proc. of IEEE International Conference on Communications*, pages 1–5, 2009.
10 Reinhard Diestel. *Graph Theory*, volume 173. Springer-Verlag, 4th edition, 2010.

11 Salim Eryigit, Suzan Bayhan, and Tuna Tugcu. Channel switching cost aware and energy-efficient cooperative sensing scheduling for cognitive radio networks. In *Proc. of IEEE International Conference on Communications (ICC)*, pages 2633–2638, 2013.

12 Giulia Galbiati. The complexity of a minimum reload cost diameter problem. *Discrete Applied Mathematics*, 156(18):3494–3497, 2008.

13 Giulia Galbiati, Stefano Gualandi, and Francesco Maffioli. On minimum changeover cost arborescences. In Panos M. Pardalos and Steffen Rebennack, editors, *Experimental Algorithms - 10th International Symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5-7, 2011. Proceedings*, volume 6630 of *Lecture Notes in Computer Science*, pages 112–123. Springer, 2011. doi:10.1007/978-3-642-20662-7_10.

14 Giulia Galbiati, Stefano Gualandi, and Francesco Maffioli. On minimum reload cost cycle cover. *Discrete Applied Mathematics*, 164:112–120, 2014.

15 Ioannis Gamvros, Luis Gouveia, and S Raghavan. Reload cost trees and network design. *Networks*, 59(4):365–379, 2012.

16 M. Garey and D. Johnson. *Computers and Intractability: A Guide to the Theory of NP-completeness*. Freeman, San Francisco, 1979.

17 Laurent Gourvès, Adria Lyra, Carlos Martinhon, and Jérôme Monnot. The minimum reload s-t path, trail and walk problems. *Discrete Applied Mathematics*, 158(13):1404–1417, 2010.

18 D. Gözüpek, S. Özkan, C. Paul, I. Sau, and M. Shalom. Parameterized complexity of the MINCCA problem on graphs of bounded decomposability. In *Proc. of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 9941 of LNCS, pages 195–206, 2016. Full version available at arXiv:1509.04880.

19 Didem Gözüpek, Seyed Buhari, and Fatih Alagöz. A spectrum switching delay-aware scheduling algorithm for centralized cognitive radio networks. *IEEE Transactions on Mobile Computing*, 12(7):1270–1280, 2013.

20 Didem Gözüpek, Hadas Shachnai, Mordechai Shalom, and Shmuel Zaks. Constructing minimum changeover cost arborescences in bounded treewidth graphs. *Theor. Comput. Sci.*, 621:22–36, 2016. doi:10.1016/j.tcs.2016.01.022.

21 Didem Gözüpek and Mordechai Shalom. Edge coloring with minimum reload/changeover costs. *Preprint available at arXiv:1607.06751*, 2016.

22 Didem Gözüpek, Mordechai Shalom, Ariella Voloshin, and Shmuel Zaks. On the complexity of constructing minimum changeover cost arborescences. *Theor. Comput. Sci.*, 540:40–52, 2014. doi:10.1016/j.tcs.2014.03.023.

23 Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. *J. Comput. Syst. Sci.*, 79(1):39–49, 2013. doi:10.1016/j.jcss.2012.04.004.

24 Finn V. Jensen. *Bayesian Networks and Decision Graphs*. Springer, 2001.

25 Vijay R Konda and Timothy Y Chow. Algorithm for traffic grooming in optical networks to minimize the number of transceivers. In *Proc. of IEEE Workshop on High Performance Switching and Routing*, pages 218–221, 2001.

26 Nasser Shami and Mehdi Rasti. A joint multi-channel assignment and power control scheme for energy efficiency in cognitive radio networks. In *Proc. of IEEE Wireless Communications and Networking Conference (WCNC)*, pages 1–6, 2016.

27 Craig A. Tovey. A simplified NP-complete satisfiability problem. *Discrete Applied Mathematics*, 8:85–89, 1984.

28 Hans-Christoph Wirth and Jan Steffan. Reload cost problems: minimum diameter spanning tree. *Discrete Applied Mathematics*, 113(1):73–85, 2001.