Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.3.pdf
  • Filesize: 0.69 MB
  • 12 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Julien Baste, Didem Gözüpek, Christophe Paul, Ignasi Sau, Mordechai Shalom, and Dimitrios M. Thilikos. Parameterized Complexity of Finding a Spanning Tree with Minimum Reload Cost Diameter. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.IPEC.2017.3

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.

Subject Classification

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

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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. Google Scholar
  2. E. Amaldi, Giulia Galbiati, and Francesco Maffioli. On minimum reload cost paths, tours, and flows. Networks, 57(3):254-260, 2011. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  7. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^kn 5-approximation algorithm for treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. Google Scholar
  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. Google Scholar
  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. Google Scholar
  10. Reinhard Diestel. Graph Theory, volume 173. Springer-Verlag, 4th edition, 2010. Google Scholar
  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. Google Scholar
  12. Giulia Galbiati. The complexity of a minimum reload cost diameter problem. Discrete Applied Mathematics, 156(18):3494-3497, 2008. Google Scholar
  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. URL: http://dx.doi.org/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. Google Scholar
  15. Ioannis Gamvros, Luis Gouveia, and S Raghavan. Reload cost trees and network design. Networks, 59(4):365-379, 2012. Google Scholar
  16. M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  20. Didem Gözüpek, Hadas Shachnai, Mordechai Shalom, and Shmuel Zaks. Constructing minimum changeover cost arborescenses in bounded treewidth graphs. Theor. Comput. Sci., 621:22-36, 2016. URL: http://dx.doi.org/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. Google Scholar
  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. URL: http://dx.doi.org/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. URL: http://dx.doi.org/10.1016/j.jcss.2012.04.004.
  24. Finn V. Jensen. Bayesian Networks and Decision Graphs. Springer, 2001. Google Scholar
  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. Google Scholar
  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. Google Scholar
  27. Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8:85-89, 1984. Google Scholar
  28. Hans-Christoph Wirth and Jan Steffan. Reload cost problems: minimum diameter spanning tree. Discrete Applied Mathematics, 113(1):73-85, 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact