Search

We study the minimum diameter spanning tree problem under the reload cost model (Diameter‐Tree for short) introduced by Wirth and Steffan. 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 Δ 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 proved that the problem can be solved in polynomial time on graphs with Δ = 3, and Galbiati proved that it is NP‐hard if Δ = 4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP‐hard if Δ = 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 Δ. [ABSTRACT FROM AUTHOR]

Golumbic, Hirst, and Lewenstein define a matching in a simple, finite, and undirected graph G to be uniquely restricted if no other matching covers exactly the same set of vertices. We consider uniquely restricted edge‐colorings of G, defined as partitions of its edge set into uniquely restricted matchings, and study the uniquely restricted chromatic index χ′ur(G) of G, defined as the minimum number of uniquely restricted matchings required for such a partition. For every graph G, χ′(G)≤a′(G)≤χ′ur(G)≤χ′s(G), where χ′(G) is the classical chromatic index, a′(G) the acyclic chromatic index, and χ′s(G) the strong chromatic index of G. While Vizing's famous theorem states that χ′(G) is either the maximum degree Δ(G) of G or Δ(G)+1, two famous open conjectures due to Alon, Sudakov, and Zaks, and to Erdős and Nešetřil concern upper bounds on a′(G) and χ′s(G) in terms of Δ(G). Since χ′ur(G) is sandwiched between these two parameters, studying upper bounds in terms of Δ(G) is a natural problem. We show that χ′ur(G)≤Δ(G)2 with equality if and only if some component of G is KΔ(G),Δ(G). If G is connected, bipartite, and distinct from KΔ(G),Δ(G), and Δ(G) is at least 4, then, adapting Lovász's elegant proof of Brooks' theorem, we show that χ′ur(G)≤Δ(G)2−Δ(G). Our proofs are constructive and yield efficient algorithms to determine the corresponding edge‐colorings. [ABSTRACT FROM AUTHOR]