Information

Event Records

16th CoRe Seminar

Date and time:  2021.10.21 Thu. 10:00-12:00
Venue:  Online
Speaker:  NAKAHATA, Yu (NAIST)
Title:  Token sliding on directed graphs
Summary: 
The Token Sliding problem (TS) is one of the most well-studied problems in combinatorial reconfiguration. In this talk, we study a directed variant of the problem: the Directed Token Sliding problem (DTS). In TS, a token can slide along an edge in both directions, while in DTS it must respect the direction of an arc, meaning that the reconfigurability is asymmetric. Since an undirected edge can be simulated by two arcs with opposite directions, DTS is a generalization of TS. In this talk, we show the hardness of DTS when the class of input graphs is limited. We also show that, as our main result, DTS can be solved in polynomial time when the input graph is a directed tree. This is a joint work with members of Groups A01 and C01, and graduate students.
Update:2021.10.08