効率的な支配集合

グラフ理論において、効率的な支配集合（ed集合または独立完全支配集合とも呼ばれる^{[ 1 ]}）とは、グラフ内のすべての頂点がその集合内のちょうど1つの頂点によって支配されるという追加の性質を持つ支配集合である。^{[ 2 ]}

効率的支配問題（ED問題）は、与えられたグラフが効率的な支配集合を含むかどうかを問う問題です。この問題は一般のグラフに対してNP完全であり^{[ 2 ]} 、 3正則平面グラフに限定した場合でもNP完全のままです^{[ 3 ]}。

頂点${\displaystyle v}$グラフでは、頂点は自身とそのすべての隣接頂点を支配する。つまり、すべての頂点は${\displaystyle u}$そのため${\displaystyle u=v}$または${\displaystyle uv\in E}$圧倒的なセット${\displaystyle D}$は、グラフ内のすべての頂点が少なくとも 1 つの頂点によって支配されるような頂点の集合です。${\displaystyle D}$効率的な支配集合は、すべての頂点がちょうど 1 つの頂点によって支配されることを要求することで、この条件を強化します。${\displaystyle D}$[ ^{2 ]​}

より厳密に言えば、頂点集合${\displaystyle D\subseteq V}$グラフにおいて${\displaystyle G=(V,E)}$は、すべての頂点に対して効率的な支配集合である。${\displaystyle v\in V}$ちょうど1つあります${\displaystyle d\in D}$そのため${\displaystyle v}$閉鎖された地域にある${\displaystyle N_{G}[d]}$の${\displaystyle d}$[ ^{2 ]​}

同等の特徴付けとしては、閉鎖された近隣地域${\displaystyle {N_{G}[d]:d\in D}}$頂点集合の分割を形成する${\displaystyle V}$[ ^{3 ]​}

効率的な支配集合は、閉じた近傍が頂点集合を分割するため、必然的に最小支配集合となる。 ^{[ 3 ]}ただし、すべての最小支配集合が効率的であるとは限らない。

効率的な支配問題は、二部グラフ、弦グラフ、弦二部グラフなど、いくつかのグラフクラスに対してNP完全である^{[ 2 ]}。この問題は、3正則平面グラフに限定した場合でもNP完全のままである^{[ 3 ] 。}

しかし、特定の制限されたグラフクラスでは、この問題は多項式時間で解決できます。 ^{[ 2 ] [ 3 ]}

• 双対弦グラフは線形時間で解くことができる
• ATフリーグラフは多項式時間で解くことができる
• 区間バイグラフは多項式時間で解くことができる
• 木構造は線形時間で解くことができる

シェルピンスキーグラフ${\displaystyle S(n,k)}$効率的な支配集合を持つグラフの注目すべき例を提供する。これらのグラフは、すべてのパラメータに対して本質的に一意の効率的な支配集合を持つ。${\displaystyle n}$そして${\displaystyle k}$[ ^{4 ] [ 5 ]​}

密接に関連するシェルピンスキーのガスケットグラフ${\displaystyle S_{n}}$シェルピンスキーのギャスケットにつながる反復から生じる は、はるかに制限的な構造を持ちます。効率的な支配集合を含むのは、 の場合のみです。${\displaystyle n=1}$または${\displaystyle n=3}$[ ^{5 ]​}

巡回グラフは、効率的な支配集合のためのよく研究された別のクラスを提供する。巡回グラフ${\displaystyle {\text{Cay}}(\mathbb {Z} _{n},S)}$は巡回群上のケイリーグラフである${\displaystyle \mathbb {Z} _{n}}$接続設定済み${\displaystyle S}$、 どこ${\displaystyle S=-S}$そして${\displaystyle 0\notin S}$このようなグラフには頂点があります。${\displaystyle \{0,1,\ldots ,n-1\}}$頂点を繋ぐ辺の差は${\displaystyle S}$[ ^{6 ]​}

巡回グラフの場合${\displaystyle {\text{Cay}}(\mathbb {Z} _{n},S)}$効率的な支配集合を認める${\displaystyle D}$必要条件は${\displaystyle n=|S_{0}|\cdot |D|}$、 どこ${\displaystyle S_{0}=S\cup \{0\}}$[ ^{6 ]​}

次数が の連結非完全巡回グラフの場合${\displaystyle |S|=p-1}$どこ${\displaystyle p}$が素数である場合、効率的な支配集合が存在するのは、${\displaystyle ss'\not \equiv 0{\pmod {p}}}$任意の異なる${\displaystyle s,s'\in S_{0}}$この条件が満たされる場合、すべての効率的な支配集合は正確に剰余類である。${\displaystyle g+p\mathbb {Z} _{n}}$のために${\displaystyle g\in \mathbb {Z} _{n}}$[ ^{6 ]​}

次数が の巡回グラフについても同様の特徴付けが存在する${\displaystyle |S|=pq-1}$そして${\displaystyle |S|=p^{m}-1}$、 どこ${\displaystyle p,q}$は素数であり、${\displaystyle m}$は正の整数である。ただし、${\displaystyle |S|+1}$比較的${\displaystyle {\frac {n}{|S|+1}}}$[ ^{6 ]​}

効率的な支配集合の概念は、2 つの研究者グループによって独立して導入されました。ノーマン・ビッグスは、1973 年に初めて、符号理論と距離推移グラフの文脈で完全符号という名前でこれらの構造を研究しました。^{[ 7 ]}その後、ビッグスの研究を知らなかったと思われるバンゲ、バルカウスカス、スレーターは、独立してこの概念を効率的な支配集合として定義し、木の中でそれらを見つけるための線形時間アルゴリズムを開発しました。^{[ 1 ] [ 3 ]}

効率的な支配集合は、並列コンピューティングにおけるリソース割り当て問題に応用できます。並列コンピュータのプロセッサと相互接続ネットワークをグラフとしてモデル化する場合、効率的な支配集合は、すべてのプロセッサが一定の距離内に位置するように、限られたリソース（ディスクドライブ、I/O接続、ソフトウェアモジュールなど）を最適に配置することを意味します。${\displaystyle d}$重複も重なりもなく、正確に1つの資源単位からなる。^{[ 3 ]}

この概念はファジーグラフや直観的ファジーグラフにも拡張され、効率的な支配が暗号化​​と復号の問題に適用されています。これらのアプリケーションでは、効率的な支配ノードが暗号化スキームのサブネットワークの中心として機能し、効率的な支配集合を特定することが復号の秘密鍵となります。^{[ 8 ]}

ハイパーキューブグラフの場合、距離 d 効率的な支配集合は、完全なバイナリ d 誤り訂正符号に正確に対応します。^{[ 3 ] [ 7 ]}このつながりは、グラフ理論の概念を符号理論に結びつけます。

効率的エッジ支配問題（EED問題）は、効率的支配問題のエッジ版である。効率的エッジ支配集合${\displaystyle M\subseteq E}$は、すべての辺が${\displaystyle e\in E}$ちょうど１つの辺と交差する${\displaystyle e'\in M}$EED問題は、弦グラフと双対弦グラフに対して線形時間で解くことができる。^{[ 2 ]}

強力で効率的な支配集合は、支配が次数が等しいかそれ以上の隣接ノードに限定される変種です。形式的には、集合は${\displaystyle S\subseteq V}$は、すべてのに対して、強力かつ効率的な支配集合である。${\displaystyle v\in V}$にはちょうど 1 つの頂点があります${\displaystyle S}$どちらも等しい${\displaystyle v}$または隣接している${\displaystyle v}$学位以上${\displaystyle \deg(v)}$標準的な効率的支配集合は、与えられたグラフ内ではすべて同じ濃度を持つが、同じグラフの強力な効率的支配集合は濃度が異なる場合がある。^{[ 9 ]}

この概念は、距離 d 完全支配集合(または距離 d PDS ) に自然に拡張されます。頂点${\displaystyle v}$頂点をd支配する${\displaystyle u}$両者間の距離が最大${\displaystyle d}$セット${\displaystyle D}$距離 d 完全支配集合とは、グラフ内のすべての頂点が、ちょうど 1 つの頂点によって d 支配されている場合を指します。${\displaystyle D}$[ ^{3 ]​}

この概念はハイパーグラフにも拡張され、同様の複雑性の結果が確立されている。^{[ 2 ]}

• スティーブン・K・グラディ著「ライフサイエンスアプリケーションのための効率的なネットワーク支配」