次数制約付き全域木

グラフ理論において、次数制約付き全域木とは、最大頂点次数が特定の定数kに制限された全域木のことである。次数制約付き全域木問題とは、特定のkに対して、特定のグラフがそのような全域木を持つかどうかを判定することである。

入力: nノードの無向グラフ G(V,E)。正の整数k < n。

質問：グラフGには、次数がkを超えるノードが存在しない全域木は存在しますか？

この問題はNP完全問題です（Garey & Johnson 1979 ） 。これはハミルトン経路問題からの還元によって示すことができます。kが2以上の値に固定されていても、NP完全問題は変わりません。問題が次数が≤ kでなければならないと定義されている場合、次数制限付き全域木のk =2のケースはハミルトン経路問題になります。  

重み付きグラフにおいて、次数制約付き最小全域木（DCMST）とは、辺の合計が最小となる次数制約付き全域木のことである。DCMSTを見つけることはNP困難問題である。^{[ 1 ]}

遺伝的アルゴリズムやアリコロニー最適化アルゴリズムなど、多項式時間で問題を解決できるヒューリスティックアルゴリズムが提案されている。

Fürer & Raghavachari (1994)は、グラフが与えられた場合に反復多項式時間アルゴリズムを提供する。${\displaystyle G}$、最大次数が以下である全域木を返します。${\displaystyle \Delta ^{*}+1}$、 どこ$\displaystyle \Delta ^{*}}$は、すべての全域木における最小の最大次数です。したがって、${\displaystyle k=\Delta ^{*}}$このようなアルゴリズムは、最大次数を持つ全域木を返すか、${\displaystyle k}$または${\displaystyle k+1}$。

完全な二部グラフの場合${\displaystyle K_{m,n}}$どこ${\displaystyle m\leq n}$:

$\displaystyle \Delta ^{*}(K_{m,n})=1+\left\lceil {\frac {n-1}{m}}\right\rceil }$

• ゲイリー、マイケル・R.、ジョンソン、デイビッド・S. (1979)、『コンピュータと難解性：NP完全性理論への手引き』、WHフリーマン、ISBN 978-0-7167-1045-5A2.1: ND1、p.206  。{{citation}}: CS1 maint: postscript (リンク)
• Fürer, Martin; Raghavachari, Balaji (1994)、「最小次数シュタイナー木を最適値の1以内まで近似する」、Journal of Algorithms、17 (3): 409–423、CiteSeerX 10.1.1.136.1089、doi : 10.1006/jagm.1994.1042。