## 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 language | English (US) |
---|---|

Title of host publication | SOFSEM 2019 |

Subtitle of host publication | Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings |

Editors | Jerzy Nawrocki, Giovanni Pighizzini, Rastislav Královič, Barbara Catania |

Publisher | Springer Verlag |

Pages | 67-80 |

Number of pages | 14 |

ISBN (Print) | 9783030108007 |

DOIs | |

State | Published - 2019 |

Event | 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 - Nový Smokovec, Slovakia Duration: Jan 27 2019 → Jan 30 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11376 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 |
---|---|

Country/Territory | Slovakia |

City | Nový Smokovec |

Period | 1/27/19 → 1/30/19 |

## Keywords

- Graph factors
- Parameterized complexity
- Reload costs

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science