最大フロー - 頂点経由 - どのように？

Question

問題：

G =（V、E）を、m> = 3の頂点上の有向グラフとし、m個の辺を持つとする。頂点集合Vは、3つの 特殊頂点a、v、およびbを含む。 aからbへの単純なパスを見つけます（存在する場合）。 （シンプルなパスとは、頂点が繰り返されていないパスです）

この問題はMax Flowアルゴリズムで解決できるはずですが、わかりません。これは、エッジに容量1がある複数のソースを持つMax Flowアルゴリズムを思い出させます。どのように問題を最大フローアルゴリズムに減らすことができるか知っていますか？

頂点bをシンクとして設定すると、vが含まれているかどうかはわかりません。vをシンクとして設定した場合、vに達するとどのように続行しますか？

Answer 1

次のように動作するはずです：

• がaからvにすべて最小限パスを見つけ、は頂点bが含まれていないこと。頂点なしでグラフ上のDFS（例えば、DFS）を得ることができますb。 a-v -path pが最小であるとし、a-v -path p'には、pの頂点のみが含まれているとします。各最小限a-v -pathため

• 、すでにa-v -pathに属する頂点を無視してvからbへのパスを探してみてください。あなたがそのようなものを見つけたら、あなたは終わった。

備考：パスの数が指数関数的に成長かもしれないが、私は私のコメントで指摘したように、少なくともこの問題の一般化バージョンは、このように、おそらく非常にされ、TSPに還元可能であると考えられること注意難しい

Answer 2

これは、3つの頂点を持つ有向パスと同型の部分グラフが含まれているかどうかを確認するのと同じです（パターンは入力グラフの頂点の一部のグラフであり、サブグラフはパターンは、サブグラフの単純な対の頂点の分離したパスにマッピングすることができる）。 Fortune, Hopcroft, and Wyllieによって、有向グラフの準同型写像は、これを含むほぼすべての固定パターンに対してNP困難であることが証明されている。したがって、問題はNP困難であり、P = NP以外のフロー技術では解決できません。

しかし、無向バージョンは、aとbをソースとシンクとすることで、最大フローに減らすことができます。