一般性を失わず\(P_i = i\) として良いので、これを仮定します。

グラフ \(G\) から次のようにグラフ \(G'\) を作ることを考えます。

• \(G\) に \(u' \le u < v \le v'\) を満たす辺 \((u, v)\) が存在する、またその時のみ \(G'\) に辺 \((u', v')\) を追加する

\(G, G'\) に対するこの問題の答えは、実は等しいことが示せます。 明らかに \(G'\) の答えのほうが大きくないので、\(G\) の答えのほうが大きくないことを示せばよいです。

ここで、\(G'\) に対しては次の2つの性質が同値になります。

• 頂点集合 \(S\) を伝えれば十分である
• \(S\) の補集合が、\(G'\) においてパスになる

これは、\((u, v)\) 間に辺がないならば、\((P_u, P_v)\) をswapした順列もよい順列になっている、つまり \(u, v\) のどちらかは伝えないといけない、ということから言えます。

そして、\(G'\) の辺数 \(K\) のパスから、\(G\) で次の条件を満たす辺集合 \((u_1 \to v_1), (u_2 \to v_2), \cdots, (u_K \to v_K)\) が容易に得られます。

• すべての \(i\) について、 \(v_i \le u_{i+1}\)

この時、\(G\) において、次の \(N - 1 - K\) 個の頂点を伝えれば十分である(= 答えの上界として \(N - 1 - K\) が得られる)ことが言えます。

• 得られた辺をパスの集合としてみなし、パスに含まれない頂点全て + 最初以外のパスの先頭の頂点を伝える
• 例: パス集合が \((a \to b \to c), (d \to e), (f \to g)\) なら \((d, f)\) + (\(a\) ~ \(g\) 以外の全ての頂点)を伝える。

よって、\(G\) の答えのほうが大きくないことを示せました。更に、このような辺集合の最大サイズを求めればよいこともわかり、これは区間スケジューリングなのでお好みの方法で高速に解くことができます。