英小文字を頂点、商品を有向辺とするグラフ \(G\) を考えます。 すると問題は以下のように言い換えられます。

\(G\) 上の walk を複数とり、どの辺も \(1\) つ以上の walk に含まれるようにする。walk の数を最小化せよ。

まず明らかに、\(G\) の弱連結成分 (有向辺を無向にしたときの連結成分)に問題を分解できます。 よって、一般性を失わず \(G\) は弱連結であるとします。

するとこの問題は最小費用循環流問題に定式化できます。 まず、\(G\) の各辺は何度でも通れるのでコスト \(0\) 容量 \(\infty\) とし、\(1\) 回以上使う必要があるので流量下限 \(1\) を設定します。 また、好きな頂点から好きな頂点への walk を作れるように、超頂点 \(T\) から各頂点へコスト \(1\) 容量 \(\infty\) の辺を、また各頂点から超頂点 \(T\) へコスト \(0\) 容量 \(\infty\) の辺を張ります。

この最小費用循環流問題の最小コストを \(k\) とすると、解は \(T\) から \(T\) へ至る \(k\) 個の walk と、\(G\) 内のいくつかのサイクルに分解されます。 \(G\) は弱連結なのでこのサイクルを全て walk の方に含めることができ、これが元の問題の解になります。 ただし \(k = 0\) かつ \(G\) の辺集合が非空の場合のみそのような調整が不可能なため、元の問題の答えが最小費用循環流の最小コストより大きく、\(1\) になります。

ACL の最小費用流ライブラリを用いると、時間計算量は \(\mathrm{O}(N^2 \log N)\) です。

追記: グラフの作り方を少し変えると、非零のコストを持つ辺を \(1\) 本にすることができます。この場合、最小費用流ではなく最大流で答えを求めることができます。