期間のあるグラフのパス

私は次の問題があります:

与えられた

  • 有向グラフ$ G =(V、E、d)$、$ d:V to mathcal {I}( mathbb {Q} _0 ^ +
    cup {+ infty })$ ここで$ mathbb {Q} _0 ^ +
    $は非負の有理数の集合を表し、$ mathcal {I}( mathbb {Q} _0 ^ + cup {+
    infty })$
    は、V $内の各頂点に関連する関数です。$ d(v)= [a、 $ {} $ {} $ {} $
    $ B $ B $ B $ >
  • V $と
  • の2つの頂点$ s、t

  • バイナリでエンコードされた整数$ h $ 、

存在するかどうかを判断しなければならない

    $ v_0 = s $と$ v_n = t $および$で、$ G_ {$ 1} $ cdot >

  • 値$ d_0、 ldots、d_n in mathbb {Q} _0 ^ + $のリスト、 すべての$ i =
    0、 ldots、n $、$ d_i d(v_i)$のように$ sum_ {i = 0} ^ n d_i =

直感的には、$ G
$内のパスを見つける必要があります。同じパスを複数回同じ頂点に置く必要があります。また、各頂点には、最小/最大期間で許容される非負の合理的な時間がありますパスの全体的な時間が$
h $に等しくなるようにする。

これはPSPACEで簡単に解決できます。
私たちはそれがNPにあると推測します(私たちはすでにそれがNP困難であることを知っています!)。例えば$ h in
Theta(2 ^ n)$があるかもしれないので、これは証明するのは簡単ではありません。したがって、必要なパスは、$ | V |
$と$ h $のバイナリエンコーディングの両方で指数関数的な長さを持つことができます。

あなたはこれまでに同様の問題を見たことがありますか?あなたはNPアルゴリズムを考え出すことができますか?あるいは、関連する文献を知っていますか?

ベストアンサー

このソリューションは、Gerhard Woeginger氏によるものです。

この問題がNPに属することを証明するために、 我々は多項式サイズの証明書を提供し、
決定論的多項式時間でそれを確認する方法を示します。

証明書は次のとおりです。 $ {x_ {u、v} mid(u、v) in E } $の集合。 直感的には、$ x_
{u、v} $は解の経路の回数です $(u、v)$をトラバースします。

ここで、 検証アルゴリズム。

  1. We consider the subset $E’$ of edges of $G$, $E’:={(u,v)in
    Emid x_{u,v}>0}$. We check whether $E’$ induces a strongly
    (undirected) connected subgraph of $G$.

  2. We check whether

    • $sum_{(u,v)in E’} x_{u,v}=sum_{(v,w)in E’} x_{v,w}$, for
      all $v in Vsetminus{s,t}$;
    • $sum_{(u,s)in E’} x_{u,s}=sum_{(s,w)in E’} x_{s,w}-1$;
    • $sum_{(u,t)in E’} x_{u,t}=sum_{(t,w)in E’} x_{t,w}+1$.
  3. For all $v in Vsetminus{s}$, we define $y_v:=sum_{(u,v)in
    E’} x_{u,v}$, i.e., the number of times the solution path gets into
    $v$. Moreover, $y_s := sum_{(s,u)in E’} x_{s,u}$.

  4. We check whether there exist real values $z_v$, for every $v in
    V$, such that

    • $d_{min}(v)cdot y_v leq z_v leq d_{max}(v)cdot y_v$ (here
      $d_{min}(v)$ and $d_{max}(v)$ denote resp. the lower and the upper
      bound of the rational interval $d(v)$), and
    • $sum_{v in V} z_v = h$.

今我々は正しいことをスケッチする:

ステップ1.と2.一緒に、円弧の値$ x_ {u、v} $が指定されていることを確認します $ s $から$ t
$への方向付けられたオイラーパス( http://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/LectureNotes/EulerianMultigraphs.pdf

ステップ3.および4.ノード$ v $上のパスの合計待ち時間である$ v in V $に対する$ z_v
$を計算する。私たちはステップ4の(等しく)同質性を観察する。
決定論的多項式時間(例えば、楕円体アルゴリズムを使用して)で解くことができる線形プログラム(LP)を形成する。

返信を残す

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