トポロジカルな最小発注コスト

$ n $頂点の有向グラフ$ G =(V、E)$が与えられ、またコスト関数$ c:V times [n] に
mathbb {R} $が与えられます。 $ v_1、 ldots、v_n
$の頂点のトポロジカルな順序を考えてみましょう。順序のコストは$ sum_ {i = 1} ^ n
c(v_i、i)$です。

低コストのトポロジカルな順序を見つけることはNP困難ですか?

ベストアンサー

Your problem is NP-hard. I show this by a reduction from the
shuffle problem: given words $w, w_1, ldots, w_k$ over
the alphabet ${a, b, c}$, decide whether $w$ can be obtained as
an interleaving (aka “shuffle”) of $w_1, ldots, w_n$. This problem
is NP-hard: see Warmuth & Haussler, On the complexity of iterated shuffle,
JCSS, 1984, Theorem 3.1.

この問題のインスタンス$ w、w_1、 ldots、w_n $が与えられ、すべての$ 1 leq i leq n
$に対して$ l_i:= | w_i | $を書くと、DAG $ G $はパスの結合として構築されますグラフ$ L_1、
ldots、L_n $、ここで、$ 1 leq i leq n $の各$ L_i $は$ l_i $頂点が$ v ^
i_1、 ldots、v ^ i_ {l_i} $と書かれています。ここで、コスト関数$ f $を以下のように定義する。各$ 1
leq i leq n $と$ 1 leq j leq l_i $に対して、$ 1 leq k leq | w |
$ごとに$ f $ w_i $の$ j $番目の文字が$ w $の$ k $番目の文字と同じであれば、(v ^ i_j、k)$は$ 0
$になり、それ以外の場合は$ 1 $となる。

この減少はPTIMEにはっきりと示されており、正確に単語$ w
$を実現するパスグラフのインターリーブがあれば、トポロジカルソートの最小コストは0であり、削減が正しいことがわかります。

(恥知らずの広告:トポロジカルソートのNP困難なバリエーションに興味がある場合は、最近のプレプリントは、固定された規則的な言語に分類されるトポロジカルなソートを見つける複雑さを研究する)

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です