本講演は標的集合と呼ばれるグラフの頂点集合の性質にまつわる遷移問題を扱う．まず，各頂点vに閾値τ(v)の割り当てられたグラフ上で次の決定的な活性化過程を考える：非活性な頂点vは，τ(v)以上の近傍頂点が活性化していたら自身も活性化し，以後非活性化しない．ある頂点集合Sの頂点のみを最初に活性化した時に，最終的に残りの頂点全てが活性化する場合，Sを「標的集合」と呼ぶ．標的集合は適当なτ(v)の下で頂点被覆・フィードバック頂点集合に対応する．また，この活性化過程はネットワーク上のある種の拡散現象を捉えているため，グラフの最小標的集合を見つける最適化問題は，バイラルマーケティングや分散コンピューティング等の動機づけが与えられている．発表者は，標的集合の遷移問題として，ある標的集合から別の標的集合に，標的集合である性質を保ちながらToken Jump操作（頂点を一つずつ交換）の列の適用で遷移できるか否かを問う判定問題を考え，その計算量解析の結果を紹介する．一般の標的集合遷移問題のPSPACE困難性は頂点被覆遷移問題の結果から直ちに示されるため，入力グラフのクラスを制限した時の容易性・困難性を解析する．特に，次数・閾値の制限時にPとPSPACE困難のどちらに属するかの境界線を探索し，また，入力グラフが木の場合に多項式時間で解けることを示す．最後に計算量が未知のクラスを紹介したい．