一旦、\(W_j\) が整数だけでなく実数の値も取れるものとして議論します。元の問題 \(\mathcal{P}\) を定式化すると以下のようになります。

\[ \begin{aligned} \max \quad & \sum_{j} W_j \\ \text{s.t.} \quad & W_{u_i} + W_{v_i} \leq 2026 & & \forall i \\ & W_j \geq 0 && \forall j \end{aligned} \]

ここで、頂点を二重化して交差するように辺を張ることで得られる以下のような問題 \(\mathcal{P}^2\) を考えます。

\[ \begin{aligned} \max \quad & \sum_{j} X_j + \sum_{j} Y_j \\ \text{s.t.} \quad & X_{u_i} + Y_{v_i} \leq 1013 & & \forall i \\ & Y_{u_i} + X_{v_i} \leq 1013 & & \forall i \\ & X_j, Y_j \geq 0 && \forall j \end{aligned} \]

この2つの問題はある意味で等価です。実際、\(\mathcal{P}\) の実行可能解 \(W\) に対して \(X = Y = \frac{1}{2}W\) とすることで \(\mathcal{P}^2\) の実行可能解を得ることができ、このとき目的関数値が変化しません。逆向きは \(W = X + Y\) を考えれば同様です。

\(\mathcal{P}^2\) は二部グラフの最大独立集合の連続緩和 (の 1013 倍) になっており、最大独立集合が整数最適解となることが知られています。二部グラフの最大独立集合を適当なアルゴリズムで計算して、最適な \(X, Y\) に対して \(W = X + Y\) とすれば \(\mathcal{P}\) の整数解が得られます。前述の等価性からこれは最適解です。