テキストの壁で申し訳ありませんが、それは私ができる限り簡潔です!
私は 1 つの非常に大きな有向グラフ G と、G 内からの頂点のサブセット S を持っています。私がやりたいことは、S によって誘導される G の部分グラフを見つけることです。 p と G の頂点 q で、誘導されたサブグラフのこれら 2 つの頂点の間にエッジが存在すること。これが重要です。通常の誘導されたサブグラフの問題よりも少し複雑です（私はそう思います）。
問題を解決するために私が考えることができる最も基本的な方法は次のとおりです（おそらく最も効率的ではないことを認識しています。実装するのに複雑すぎない他の提案があれば教えてください）：S内の頂点のすべてのペアについて、G でそれらの間のパスの存在をテストします。そのようなパスが存在する場合、誘導された部分グラフの p と q の間にエッジを挿入します。私の目的では、n^2 時間はそれほど悪くありません。
したがって、2 つの質問があると思います。1) 2 つの頂点間にパスが存在するかどうかを判断する最速の方法は何ですか? パスが存在するかどうかだけで、パスを知る必要はありません。さらに、この計算を高速化するためにグラフ全体に対して実行できる前処理がある場合、頂点の各ペア間でこの計算を実行する必要があるため、それは何でしょうか?
2）私が説明した誘導サブグラフのタイプを見つけるために私が提案した方法よりも速い方法はありますか？
助けてくれてどうもありがとう！