トークンスライディング問題（TS問題）は組合せ遷移において最もよく研究されている問題のひとつである．本講演ではこの問題の有向グラフ版である有向トークンスライディング問題（有向TS問題）を考える．TS問題ではトークンを辺の向きに沿ってどちら向きにも動かせるが，有向TS問題ではトークンを辺の向きに沿ってしか動かせないという非対称性がある．無向辺は逆向きの2つの有向辺で模倣できるため，有向TS問題はTS問題の一般化である．本講演では，有向TS問題に対して，グラフクラスを限定した場合の困難性を示す．また，主結果として，入力が木を向き付けたグラフの場合に多項式時間で解けることを示す．本講演の内容はA01班，C01班のメンバーと大学院生を含む共同研究に基づく．