Minimum reload cost graph factors

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The concept of Reload cost in a graph refers to the cost that occurs while traversing a vertex via two of its incident edges. This cost is uniquely determined by the colors of the two edges. This concept has various applications in transportation networks, communication networks, and energy distribution networks. Various problems using this model are defined and studied in the literature. The problem of finding a spanning tree whose diameter with respect to the reload costs is the smallest possible, the problems of finding a path, trail or walk with minimum total reload cost between two given vertices, problems about finding a proper edge coloring of a graph such that the total reload cost is minimized, the problem of finding a spanning tree such that the sum of the reload costs of all paths between all pairs of vertices is minimized, and the problem of finding a set of cycles of minimum reload cost, that cover all the vertices of a graph, are examples of such problems. In this work we focus on the last problem. Noting that a cycle cover of a graph is a 2-factor of it, we generalize the problem to that of finding an r-factor of minimum reload cost of an edge colored graph. We prove several NP-hardness results for special cases of the problem. Namely, bounded degree graphs, planar graphs, bounded total cost, and bounded number of distinct costs. For the special case of r=2, our results imply an improved NP-hardness result. On the positive side, we present a polynomial-time solvable special case which provides a tight boundary between the polynomial and hard cases in terms of r and the maximum degree of the graph. We then investigate the parameterized complexity of the problem, prove W[1]-hardness results and present an FPT-algorithm.

Original languageEnglish (US)
Title of host publicationSOFSEM 2019
Subtitle of host publicationTheory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
EditorsJerzy Nawrocki, Giovanni Pighizzini, Rastislav Královič, Barbara Catania
PublisherSpringer Verlag
Pages67-80
Number of pages14
ISBN (Print)9783030108007
DOIs
StatePublished - 2019
Event45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 - Nový Smokovec, Slovakia
Duration: Jan 27 2019Jan 30 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11376 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
Country/TerritorySlovakia
CityNový Smokovec
Period1/27/191/30/19

Keywords

  • Graph factors
  • Parameterized complexity
  • Reload costs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Minimum reload cost graph factors'. Together they form a unique fingerprint.

Cite this