Reconfiguration of Time-Respecting Arborescences

• Published in: arXiv.org 2023-06
• Main Authors: Ito, Takehiro, Iwamasa, Yuni, Kamiyama, Naoyuki, Kobayashi, Yasuaki, Kobayashi, Yusuke, Maezawa, Shun-ichi, Suzuki, Akira
• Format: Article
• Language: English
• Subjects: Combinatorial analysis; Fields (mathematics); Graph theory; Polynomials; Reconfiguration
• ISSN: 2331-8422

An arborescence, which is a directed analogue of a spanning tree in an undirected graph, is one of the most fundamental combinatorial objects in a digraph. In this paper, we study arborescences in digraphs from the viewpoint of combinatorial reconfiguration, which is the field where we study reachability between two configurations of some combinatorial objects via some specified operations. Especially, we consider reconfiguration problems for time-respecting arborescences, which were introduced by Kempe, Kleinberg, and Kumar. We first prove that if the roots of the initial and target time-respecting arborescences are the same, then the target arborescence is always reachable from the initial one and we can find a shortest reconfiguration sequence in polynomial time. Furthermore, we show if the roots are not the same, then the target arborescence may not be reachable from the initial one. On the other hand, we show that we can determine whether the target arborescence is reachable form the initial one in polynomial time. Finally, we prove that it is NP-hard to find a shortest reconfiguration sequence in the case where the roots are not the same. Our results show an interesting contrast to the previous results for (ordinary) arborescences reconfiguration problems.