Abstract
We study the minimum diameter spanning tree problem under the reload cost model (DIAMETERTREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edgecolored 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 DIAMETERTREE 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 DIAMETERTREE is paranphard 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 DIAMETERTREE to be NPhard 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 NPhard if Delta=4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NPhard 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 DIAMETERTREE is in XP and W[1]hard parameterized by the treewidth plus Delta.
BibTeX  Entry
@InProceedings{baste_et_al:LIPIcs:2018:8554,
author = {Julien Baste and Didem G{\"o}z{\"u}pek and Christophe Paul and Ignasi Sau and Mordechai Shalom and Dimitrios M. Thilikos},
title = {{Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {3:13:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8554},
URN = {urn:nbn:de:0030drops85545},
doi = {10.4230/LIPIcs.IPEC.2017.3},
annote = {Keywords: reload cost problems, minimum diameter spanning tree, parameterized complexity, FPT algorithm, treewidth, dynamic programming}
}
Keywords: 

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

12th International Symposium on Parameterized and Exact Computation (IPEC 2017) 
Issue Date: 

2018 
Date of publication: 

02.03.2018 