計算複雑性理論および組合せ論では、トークン再構成問題は、トークンの初期状態および所望状態の両方を有するグラフ上の最適化問題である。
グラフ${\displaystyle G}$が与えられると、トークンの初期状態は、グラフの頂点のサブセット${\displaystyle V\subset V(G)}$によって定義される。 let ${\displaystyle n=|V|}$とする。頂点${\displaystyle v_{1}}$から頂点${\displaystyle v_{2}}$へのトークンの移動は、${\displaystyle v_{1}}$と${\displaystyle v_{2}}$が他のトークンを含まない${\displaystyle G}$のパスで結合されている場合に有効です。グラフ内を移動する距離は重要ではなく、トークンを複数のエッジに順次移動させることは1回の移動とみなされます。所望の終了状態は別のサブセット${\displaystyle V’\subset V(G)}$として定義される。目標は、初期状態から終了状態に達する有効な移動の回数を最小限に抑えることです。