\(2\) 部グラフの完全マッチング（最大流）問題と強連結成分分解を組み合わせることで，この問題を解くことができます． これは所謂 DM 分解 (Dulmage–Mendelsohn decomposition) の応用です．

密度が $D$ より真に大きい誘導部分グラフの存在判定

まず，密度が \(D\) より真に大きい誘導部分グラフが存在するかどうかを判定することを考えます． 空でない頂点真部分集合 \(X\) が存在して，\(X\) による誘導部分グラフの密度が \(D\) より真に大きいとします． これは，空でない頂点真部分集合 \(Y\) が存在して，\(Y\) 内に少なくとも一方の端点を持つ辺の数が \(D \cdot |Y|\) 未満であることと同値です．（ \(X\) の補集合が \(Y\) に対応します．）

ここで，\(G\) における頂点と辺の接続関係を表す \(2\) 部グラフ \(H\) を考えます． すなわち，入力グラフ \(G\) の各頂点を左側頂点，\(G\) の各辺を右側頂点とし，\(G\) の各辺 \(e = (u, w)\) について \((u, e)\), \((w, e)\) の \(2\) 本の辺を張って得られる，\((N + DN)\) 頂点 \(2DN\) 辺の \(2\) 部グラフを \(H\) とします． \(H\) 上で，左側（頂点側）の各頂点の容量を \(D\)，右側（辺側）の各頂点の容量を \(1\) とした完全マッチング問題（各左側頂点についてちょうど \(D\) 本ずつ，各右側頂点についてちょうど \(1\) 本ずつとなるように辺を選ぶ問題）を考えます． Hall の定理（の素朴な拡張）より，判定したい条件は，この頂点容量付き \(2\) 部グラフ \(H\) が完全マッチングを持たないことと同値となります．

以上より，\(H\) における頂点容量付き完全マッチング問題を解けばよいです． これは，Hopcroft–Karp のアルゴリズムを素朴に拡張したり，最大流問題に帰着して Dinic のアルゴリズムを適用したりすることで，\(\mathrm{O}((DN)^{1.5})\) 時間で可能です．

密度がちょうど $D$ である誘導部分グラフの存在判定

上記の頂点容量付き \(2\) 部グラフ \(H\) が完全マッチングを持つ場合に，密度がちょうど \(D\) である誘導部分グラフが \(G\) 自身以外に存在するかどうかを判定することを考えます． \(H\) における完全マッチングの存在は，\(G\) の各頂点にちょうど \(D\) 本ずつの接続辺を互いに重ならないように割り当てられることを意味します． その割当てに従って，\(G\) の全ての辺を「割り当てられた頂点から出る」ように向き付けて得られる有向グラフを \(\vec{G}\) とします． このとき，判定したい条件は，\(\vec{G}\) が強連結でないことと同値となります．

まず，\(\vec{G}\) が強連結でないとします． このとき，出る辺が存在しないような強連結成分を任意に \(1\) つ選んで，その頂点集合を \(X\) とします． すると，\(X\) 内の頂点に割り当てられた \(D \cdot |X|\) 本の辺は全て \(X\) 内の \(2\) 頂点を結んでおり，\(X\) による誘導部分グラフの密度が \(D\) 以上であることが従います． また，密度が \(D\) より真に大きい誘導部分グラフの存在は既に排除されているので，ちょうど \(D\) となります．

逆に，空でない頂点真部分集合 \(X\) が存在して，\(X\) による誘導部分グラフの密度がちょうど \(D\) であるとします． このとき，\(X\) 内の \(2\) 頂点を結ぶ \(D \cdot |X|\) 本の辺は全て \(X\) 内の頂点に割り当てられている必要があり，\(\vec{G}\) において \(X\) から出る辺は存在しません． したがって，\(\vec{G}\) は強連結ではありません．

\(\vec{G}\) は \(N\) 頂点 \(DN\) 辺の有向グラフなので，その強連結成分分解は \(\mathrm{O}(DN)\) 時間で計算できます． 以上より，全体として \(\mathrm{O}((DN)^{1.5})\) 時間でこの問題を解くことができます．

実装例 (Dinic) (C, 1163 ms)
実装例 (Hopcroft–Karp) (C, 83 ms)