支配的なセット

同じグラフの 3 つの支配集合 (赤)。このグラフの支配数は 2 です。(b) と (c) は、2 つの頂点を持つ支配集合が存在し、1 つの頂点のみを持つ支配集合は存在しないことを示しています。

グラフ理論において、グラフ $G$ の支配集合とは、その頂点の部分集合 $Dであり、$ $G$ の任意の頂点は $D$ に含まれるか、または $D$ 内に隣接する頂点を持つ。支配数 $γ($ $G$ $)は、$ $G$ の最小の支配集合に含まれる頂点の数である。

支配集合問題は、与えられたグラフ $G$ と入力 $Kに対して$ $γ(G) \leq K$ であるかどうかをテストすることに関するもので、計算複雑性理論における古典的なNP 完全決定問題です。^[1]したがって、すべてのグラフ $G$ $に対してγ($ $G$ $)$ を計算できる効率的なアルゴリズムは存在しないと考えられています。ただし、特定のグラフクラスに対しては効率的な近似アルゴリズムと効率的な厳密アルゴリズムが存在します。

支配集合は、いくつかの分野で実用的に興味深いものです。ワイヤレスネットワークでは、支配集合はアドホックモバイルネットワーク内で効率的なルートを見つけるために使用されます。また、ドキュメントの要約や電力網の安全なシステムの設計にも使用されています。

正式な定義

無向グラフ $G = (V, E)$ が与えられたとき、すべての頂点に対してとなる頂点が存在する場合、頂点のサブセットは支配集合と呼ばれます。 $D\subseteq V$ $u\in V\setminus D$ $v\in D$ $(u,v)\in E$

すべてのグラフには少なくとも 1 つの支配集合があります。すべての頂点の集合が $D$ である場合、頂点は存在しないため、定義によりDは支配集合です。より興味深い課題は、小さな支配集合を見つけることです。Gの支配数は次のように定義されます。 $D=V=$ $u\in V\setminus D$ ${\displaystyle \gamma (G):=\min\{|D|:D{\text{ は }}G\}} の支配集合である$

バリエーション

連結支配集合は、連結されている支配集合です。Sが連結支配集合である場合、S が木の非葉頂点の集合を形成する G の全域木を形成できます。逆に、T が 3 つ以上の頂点を持つグラフ内の任意の全域木である場合、Tの非葉頂点は連結支配集合を形成します。したがって、連結支配集合の最小値を見つけることは、葉の数が最大となる全域木を見つけることと同じです。

全支配集合（または強く支配する集合）は、グラフ内のすべての頂点（支配集合内の頂点自体も含む）が、支配集合内に隣接する頂点を持つような頂点の集合である。^[2]つまり、すべての頂点に対して、となる頂点が存在する。上の図 (c) は、連結支配集合かつ全支配集合である支配集合を示している。図 (a) と (b) の例はどちらでもない。単純支配集合とは対照的に、全支配集合は存在しない可能性がある。たとえば、1 つ以上の頂点を持ち、辺を持たないグラフには、全支配集合はない。G $の$ 強い支配数はと定義される。明らかに、である。 $u\in V$ $v\in D$ $(u,v)\in E$ ${\displaystyle \gamma ^{strong}(G):=\min\{|D|:D{\text{ は }}G\}} の強い支配集合である$ $\gamma ^{strong}(G)\geq \gamma (G)$

支配辺集合とは、その和が支配集合となる辺（頂点のペア）の集合です。このような集合は存在しない場合もあります（たとえば、1 つ以上の頂点を持ち、辺を持たないグラフには支配集合はありません）。支配集合が存在する場合、そのすべての辺の和は強く支配する集合です。したがって、辺支配集合の最小サイズは少なくともです。 $\gamma^{strong}(G)/2$

対照的に、エッジ支配集合は、 Dに含まれないすべてのエッジがD内の少なくとも 1 つのエッジに隣接するようなエッジの集合Dです。このような集合は常に存在します (たとえば、すべてのエッジの集合はエッジ支配集合です)。

k支配集合は、集合に含まれない各頂点がその集合内に少なくともk 個の隣接頂点を持つような頂点の集合である（標準支配集合は 1 支配集合である）。同様に、k組支配集合は、グラフ内の各頂点がその集合内に少なくともk 個の隣接頂点を持つような頂点の集合である（全支配集合は 1 組支配集合である）。最小のk組支配集合の $(1 + log n)$ 近似は、多項式時間で求めることができる。^[3]すべてのグラフはk支配集合（たとえば、すべての頂点の集合）を持つことができるが、最小次数が $k$ $- 1であるグラフだけが$ k組支配集合を持つことができる。しかし、グラフがk組支配集合を持つとしても、最小のk組支配集合は、同じグラフの最小のk支配集合のほぼk倍になることがある。 ^[4]最小k支配集合の $(1.7 + logΔ)$ 近似も多項式時間で求めることができる。

スター支配集合 とは、Vのサブセット Dで、 Vのすべての頂点vについて、vのスター( vに隣接する辺の集合) がDのいくつかの頂点のスターと交差する集合のことである。明らかに、 G に孤立した頂点がある場合、スター支配集合は存在しない (孤立した頂点のスターは空であるため)。 G に孤立した頂点がない場合、すべての支配集合はスター支配集合であり、その逆も同様である。スター支配と通常の支配の違いは、それらの分数的な変種を考慮すると、より顕著になる。^[5]

ドマティックパーティションは、頂点を互いに交わらない支配集合に分割することです。ドマティック数は、ドマティックパーティションの最大サイズです。

永遠支配集合は、支配集合D内の頂点vが選択され、近傍の頂点u ( uはD内にない) に置き換えられる、動的な支配バージョンです。これにより、変更されたDも支配集合となり、このプロセスは頂点vの選択の無限シーケンスにわたって繰り返すことができます。

支配集合と独立集合

支配集合は独立集合と密接に関連しています。独立集合は、最大独立集合である場合にのみ支配集合でもあります。したがって、グラフ内の任意の最大独立集合は、必然的に最小の支配集合でもあります。

支配による独立集合

支配集合は独立集合である場合もそうでない場合もあります。たとえば、上の図 (a) と (b) は独立支配集合を示していますが、図 (c) は独立集合ではない支配集合を示しています。

グラフ $Gの$ 独立支配数 i $(G) は$ 、独立集合である最小の支配集合のサイズです。同様に、最小の最大独立集合のサイズです。 $i$ $($ $G$ $)$ の最小値は、より少ない要素（独立集合のみを考慮する）で取得されるため、すべてのグラフ $G$ に対して $γ$ $($ $G$ $) \leq$ $i$ $($ $G$ $)$ です。

不等式は厳密になる可能性があります。つまり、 $γ$ $($ $G$ $) <$ $i$ $($ $G$ $)$ となるグラフ $G$ が存在します。たとえば、 $G が$ $p$ $、$ $q$ $> 1$ となる頂点⁠ ⁠からなる二重星型グラフであるとします。 $G$ の辺は次のように定義されます。各 $x$ $i$ $はa$ に隣接し、 $aは$ $b$ に隣接し、 $b は各$ $y$ $j$ に隣接します。この場合、 ${$ $a$ $、$ $b$ $} は$ 最小の支配集合であるため、 $γ($ $G$ $) = 2 となります。$ $p$ $\leq$ $q$ の場合、⁠ ⁠ は最小の支配集合であり、独立でもあるため(最小の最大独立集合であるため) 、 $i$ $($ $G$ $) =$ $p$ $+ 1となります。$ $x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}$ $\{x_{1},\ldots ,x_{p},b\}$

$γ(G)= i (G)$ となるグラフ族が存在する。つまり、すべての最小最大独立集合は最小支配集合である。例えば、 $Gが$ クローフリーグラフである場合、 $γ(G)= i (G)$ となる。^[6]

グラフ $Gは、$ $G$ のすべての誘導部分グラフ $H$ において $γ$ $($ $H$ $) =$ $i$ $($ $H$ $)$ が成り立つとき、支配完全グラフと呼ばれる。クローフリーグラフの誘導部分グラフはクローフリーであるため、すべてのクローフリーグラフも支配完全であることがわかる。^[7]

任意のグラフ $G$ について、その線グラフ $L (G)$ はクローフリーであるため、 $L (G)の最小最大独立集合は$ $L (G)$ の最小支配集合でもあります。 $L (G)$ の独立集合は $G$ のマッチングに対応し、 $L$ $($ $G$ $)の支配集合は$ $G$ の辺支配集合に対応します。したがって、最小最大マッチングは最小辺支配集合と同じサイズです。

支配の独立集合

グラフ $Gの$ 独立支配数 iγ $(G) は、$ $G$ のすべての独立集合 $Aにおいて、$ $A$ を支配する最小の集合の最大値である。^[8]頂点のサブセットを支配するには、すべての頂点を支配する場合よりも必要な頂点の数が少なくなる可能性があるため、すべてのグラフ $G$ について $iγ$ $($ $G$ $) \leq$ $γ$ $($ $G$ $)$ が成り立ちます。

不等式は厳密になる可能性があり、 $iγ$ $($ $G$ $) <$ $γ$ $($ $G$ $)$ となるグラフ $G$ が存在します。たとえば、ある整数 $n$ に対して、 $G が$ $n$ バイ $n の$ ボードの行と列を頂点とするグラフであるとします。このような 2 つの頂点は、交差する場合に限り連結されます。独立した集合は行のみの集合または列のみの集合のみであり、それらのそれぞれは単一の頂点 (列または行) によって支配されるため、 $iγ$ $($ $G$ $) = 1 と$ なります。ただし、すべての頂点を支配するには、少なくとも 1 つの行と 1 つの列が必要なため、 $γ$ $($ $G$ $) = 2 となります。さらに、$ $γ$ $($ $G$ $) /$ $iγ$ $($ $G$ $)$ の比率は任意の大きさになる場合があります。たとえば、 $G$ の頂点がすべて $n$ バイ $n の$ ボードの正方形の部分集合である場合、 $iγ$ $($ $G$ $) = 1$ のままですが、 $γ$ $($ $G$ $) = n と$ なります。^[8]

グラフ $G$ の双独立支配数 $iγi (G)は、$ $G$ のすべての独立集合 $Aの中で、$ $A$ を支配する最小の独立集合の最大値です。任意のグラフ $G$ に対して次の関係が成り立ちます。 ${\begin{aligned}i(G)&\geq \gamma (G)\geq i\gamma (G)\\i(G)&\geq i\gamma i(G)\geq i\gamma (G)\end{整列}}$

歴史

支配問題は1950年代から研究されてきたが、支配に関する研究は1970年代半ばに大幅に増加した。1972年、リチャード・カープは集合被覆問題がNP完全であることを証明した。これは支配集合問題に直接的な影響を与えた。なぜなら、2つの問題の間には頂点から集合への、また辺から非分離交差への直接的な一対一変換が存在するからである。これにより支配集合問題もNP完全であることが証明された。 ^[9]

アルゴリズムと計算の複雑さ

集合被覆問題はよく知られたNP 困難問題である。集合被覆の決定版は、カープの 21 個の NP 完全問題の 1 つであった。最小支配集合問題と集合被覆問題の間には、多項式時間のL 簡約が1 組存在する。^[10]これらの簡約 (下記参照) は、最小支配集合問題の効率的なアルゴリズムが集合被覆問題の効率的なアルゴリズムを提供することを示しており、その逆もまた同様である。さらに、簡約は近似比を保存する。つまり、任意の α に対して、最小支配集合の多項式時間α 近似アルゴリズムは集合被覆問題の多項式時間α 近似アルゴリズムを提供し、その逆もまた同様である。どちらの問題も、実際にはLog-APX 完全である。^[11]

集合被覆の近似可能性もよく理解されている。対数近似係数は単純な貪欲アルゴリズムを使用して見つけることができ、対数近似係数を見つけることはNP困難である。より具体的には、貪欲アルゴリズムは最小支配集合の係数 $1 + log| V |近似を提供し、$ P = NPでない限り、多項式時間アルゴリズムは $c$ $> 0$ に対して $c log| V |$ よりも優れた近似係数を達成できない。^[12]

L還元

次の2つの還元は、最小支配集合問題と集合被覆問題がL還元の下では同等であることを示しています。つまり、一方の問題のインスタンスが与えられた場合、もう一方の問題の同等のインスタンスを構築することができます。^[10]

支配的なセットからセットをカバーするまで

グラフ $G = (V, E)$ で $V = {1, 2, ..., n} が与えられた場合、$ 集合カバーインスタンス $(U, S)$ を次のように構築します。宇宙 $Uは$ $V$ であり、部分集合の族は $S = {S 1, S 2, ..., S n}$ であり、 $S v$ $はG$ 内の頂点 $vと$ $v$ に隣接するすべての頂点で構成されます。

$ここで、 D が$ $G$ の支配集合である場合、 $C = {S v : v \in D} は$ 集合被覆問題の実行可能解であり、 $| C | = | D |$ となります。逆に、 $C = {S v : v \in D}$ が集合被覆問題の実行可能解である場合、 $D は$ $G$ の支配集合であり、 $| D | = | C |$ となります。

$したがって、 G$ の最小支配集合のサイズは、 $(U 、 S)$ の最小集合被覆のサイズに等しくなります。さらに、支配集合を同じサイズの集合被覆にマッピングする簡単なアルゴリズムがあり、その逆もあります。特に、集合被覆の効率的なα 近似アルゴリズムは、最小支配集合の効率的なα 近似アルゴリズムを提供します。

たとえば、右に示すグラフ

G

が与えられた場合、集合

U = {1, 2, ..., 6}

と部分集合

S 1 = {1, 2, 5}、

S 2 = {1, 2, 3, 5}、

S 3 = {2, 3, 4, 6}、

S 4 = {3, 4}、

S 5 = {1, 2, 5, 6}、

および

S 6 = {3, 5, 6} を持つ集合被覆インスタンスを構築します。

この例では、

D = {3, 5}は

G

の支配集合です。これは集合被覆

C = {S 3 、 S 5} に対応します。

たとえば、頂点

4 \in V は

頂点3 \in D

によって支配され、要素

4 \in U

は集合

S 3 \in C

に含まれます。

セットカバーからセット支配へ

$(S, U)$ を、集合 $U$ と部分集合の族 $S = {S i : i \in I} を持つ集合被覆問題のインスタンスとします。U$ と $インデックス$ 集合 $I は$ 互いに素であると仮定します。グラフ $G = (V, E)$ を次のように構築します。頂点の集合は $V = I \cup U$ で、各ペア $i$ $、$ $j$ $\in$ $I$ $間には辺{i 、 j} \in E$ があり、各 $i$ $\in$ $I$ および $u$ $\in$ $S$ $i$ に対しても辺 ${$ $i$ $、$ $u$ $}$ が存在します。つまり、 $G は$ 分割グラフです。I $は$ クリークであり、 $U は$ 独立集合です。

ここで、 $C = {S i : i \in D}が何らかの部分集合$ $D \subseteq I$ に対する集合被覆問題の実行可能解である場合、 $D は$ $G$ の支配集合となり、 $| D | = | C |$ となります。まず、各 $u \in Uに対して、$ $u$ $\in$ $S$ $i$ となる $i \in D$ が存在し、構築により、 $u$ と $i は$ $G$ で隣接しているため、 $uは$ $i$ に支配されます。次に、 $D は$ 空でなければならないため、各 $i$ $\in$ $I$ $はD$ の頂点に隣接します。

逆に、 $D を$ $G$ の支配集合とします。このとき、 $|$ $X$ $| \leq |$ $D$ $|$ かつ $X$ $\subseteq$ $I$ となるような別の支配集合 $X を$ 構築することができます。つまり、各 $u$ $\in$ $D$ $\cap$ $U を$ $u$ の近傍 $i$ $\in$ $I$ に置き換えるだけです。すると、 $C$ $= {$ $S$ $i$ $:$ $i$ $\in$ $X$ $} は$ 集合被覆問題の実行可能な解となり、 $|$ $C$ $| = |$ $X$ $| \leq |$ $D$ $|$ となります。

右の図は、

U = {a 、 b 、 c 、 d 、 e}、 I = {1、2、3、4}、

S 1 = {a 、 b 、 c}、

S 2 = {a、b}、S

3

=

{

b

、

c 、 d

}

、

S

4

=

{

c

、

d

、

e

}

の

構築

を

示してい

ます。

この例では、

C = {S 1 、 S 4}

は集合被覆であり、これは支配集合

D = {1、4} に対応します。

D = {a, 3, 4}

はグラフ

G

の別の支配集合です。

D

が与えられれば、

D

より大きくなく

I

のサブセットである

支配集合X = {1, 3, 4}

を構築できます。支配集合

X は

集合被覆

C

= {

S

1

,

S

3

,

S

4

} に対応します。

特別なケース

グラフの最大次数 Δ の場合、貪欲近似アルゴリズムは最小支配集合の $O (log Δ)$ 近似を見つけます。また、貪欲近似を使用して得られた支配集合の濃度を $d g$ とすると、次の関係が成立します。ここで、 $N$ はノードの数、 $M は$ 与えられた無向グラフのエッジの数です。^{[13] Δ が固定されている場合、これは}APXメンバーシップの支配集合として適格であり、実際、APX 完全です。^[14] $d_{g}\leq N+1-{\sqrt {2M+1}}$

この問題は、単位円グラフや平面グラフなどの特殊なケースに対しては多項式時間近似スキーム（PTAS）を許容する。^[15]直列並列グラフでは最小支配集合を線形時間で見つけることができる。^[16]

正確なアルゴリズム

$n$ 頂点グラフの最小支配集合は、すべての頂点サブセットを調べることで、時間 $O (2 n n)で見つけることができます。Fomin、Grandoni、Kratsch (2009) は、時間$ $O (1.5137 n)$ と指数空間、および時間 $O (1.5264 n)と多項式空間で最小支配集合を見つける方法を示しています。O$ $(1.5048$ $n$ $)$ $時間$ を使用するより高速なアルゴリズムは、van Rooij、Nederlof、van Dijk (2009) によって発見され、最小支配集合の数もこの時間で計算できることが示されています。最小支配集合の数は最大で $1.7159 n$ $であり、そのような集合はすべて時間O (1.7159 n)$ でリストできます。^[17]

パラメータ化された複雑さ

$サイズk$ の支配集合を見つけることは、パラメータ化された複雑性の理論において中心的な役割を果たしている。これはクラスW[2]の最もよく知られた完全な問題であり、他の問題の扱いにくさを示すために多くの還元に使用されている。特に、この問題は、W階層がFPT=W[2]に崩壊しない限り、任意の関数 $f$ に対して実行時間 $f (k) nO (1)のアルゴリズムが存在しないという意味で、固定パラメータでは扱いにくい。$

一方、入力グラフが平面グラフの場合、問題は依然として NP 困難ですが、固定パラメータアルゴリズムが知られています。実際、この問題は $k$ に線形のサイズのカーネルを持ち、^{[18]カーネルの}分岐分解に動的計画法を適用することで、 √ k $に指数関数的かつn$ に 3 乗の実行時間を得ることができます。^[19]より一般的には、支配集合問題とその多くの変種は、支配集合のサイズと最小の禁制完全二部グラフのサイズの両方でパラメータ化されている場合、固定パラメータで扱いやすくなります。つまり、問題は、平面グラフを含む非常に一般的なクラスのスパースグラフである、二クリークフリーグラフ上の FPT です。^[20]

支配集合の補集合である非ブロッカーは、任意のグラフ上で固定パラメータアルゴリズムによって見つけることができます。^[21]

参照

ヴィジングの予想-グラフの直積の支配数とその因子の支配数を関連付けます。
セットカバーの問題
ボンデージナンバー
非ブロッカー- 支配セットの補数。

注記

^ ギャリー＆ジョンソン（1979年）。
^ West（2001）、セクション3.1。
^ Klasing & Laforest (2004).
^ フォルスター（2013年）。
^ Meshulam, Roy (2003-05-01). 「支配数とホモロジー」. Journal of Combinatorial Theory, Series A. 102 ( 2): 321–330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165.
^ アラン＆ラスカー（1978年）。
^ Faudree、Flandrin、Ryjáček（1997年）。
^ ab アハロニ、ロン;バーガー、イーライ。ジヴ、ラン (2007-05-01)。「加重グラフにおける代表者の独立したシステム」。コンビナトリカ。27 (3): 253–267。土井：10.1007/s00493-007-2086-y。ISSN 1439-6912。S2CID 43510417。
^ ヘデトニエミ＆ラスカー（1990）。
^ ab Kann (1992)、108–109 ページ。
^ エスコフィエ＆パスコス（2006年）。
^ ラズ＆サフラ（1997年）。
^ パレック（1991年）。
^ パパディミトリウとヤナカキス (1991)。
^ クレセンツィ他（2000年）。
^ 高見沢・西関・斉藤 (1982).
^ フォミンら（2008年）。
^ アルバー、フェローズ、ニーダーマイヤー (2004)。
^ フォミン＆ティリコス（2006年）。
^ テル＆ヴィランジェ（2012年）。
^ デーンら（2006年）。

参考文献

アルバー、ヨッヘン;フェローズ、マイケル R ;ニーダーマイヤー、ロルフ(2004)、「支配集合の多項式時間データ削減」、Journal of the ACM、51 (3): 363–384、arXiv : cs/0207066、doi :10.1145/990308.990309、S2CID 488501。
アラン、ロバート B.; ラスカー、レヌ (1978)、「グラフの支配数と独立支配数について」、離散数学、23 (2): 73–76、doi : 10.1016/0012-365X(78)90105-X。
クレッシェンツィ、ピエルルイジ。カン、ヴィゴ。ハルドルソン、マグナス。Karpinski, マレク; Woeginger、Gerhard (2000)、「最小支配集合」、NP 最適化問題の概要。
Dehne, Frank; Fellows, Michael; Fernau, Henning; Prieto, Elena ; Rosamond, Frances (2006)、「Nonblocker: 最小支配集合のパラメータ化アルゴリズム」(PDF)、SOFSEM 2006: 32nd Conference on Current Trends in Theory and Practice of Computer Science、Merin、チェコ共和国、2006 年 1 月 21 ～ 27 日、議事録、Lecture Notes in Computer Science、vol. 3831、Springer、pp. 237 ～ 245、doi :10.1007/11611257_21、ISBN 978-3-540-31198-0。
Escoffier, Bruno; Paschos, Vangelis Th. (2006)、「APX を超える近似クラスの完全性」(PDF)、理論計算機科学、359 (1–3): 369–377、doi : 10.1016/j.tcs.2006.05.023
フォードリー、ラルフ; フランドリン、エヴェリン; リャチェク、ズデニェク (1997)、「クローフリーグラフ - 概観」、離散数学、164 (1–3): 87–147、doi : 10.1016/S0012-365X(96)00045-3、MR 1432221。
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009)、「正確なアルゴリズムの分析のための測定と征服アプローチ」、Journal of the ACM、56 (5): 25:1–32、doi :10.1145/1552285.1552286、S2CID 1186651。
Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008)、「測定と統治による組み合わせ境界: 最小支配集合の境界設定とアプリケーション」、ACM Transactions on Algorithms、5 (1): 9:1–17、doi :10.1145/1435375.1435384、S2CID 2489447。
Fomin, Fedor V.; Thilikos, Dimitrios M. (2006)、「平面グラフの支配集合: 分岐幅と指数関数的高速化」、SIAM Journal on Computing、36 (2): 281、doi :10.1137/S0097539702419649、S2CID 5232238。
Förster, Klaus-Tycho. (2013)、「一般グラフにおけるフォールトトレラント支配の近似」、解析アルゴリズムと組合せ論に関する第 10 回ワークショップ論文集ANALCO、SIAM、pp. 25–32、doi :10.1137/1.9781611973037.4、ISBN 978-1-61197-254-2。
ゲーリー、マイケル R. ;ジョンソン、デビッド S. (1979)。コンピュータと扱いにくさ: NP 完全性理論ガイド。数学科学シリーズ (第 1 版)。ニューヨーク: WH フリーマンアンドカンパニー。ISBN 9780716710455. MR 0519066. OCLC 247570676.、190ページ、問題GT2。
Hedetniemi, ST; Laskar, RC (1990)、「グラフにおける支配に関する参考文献と支配パラメータの基本定義」、離散数学、86 (1–3): 257–277、doi : 10.1016/0012-365X(90)90365-O。
Kann, Viggo (1992)、「NP完全最適化問題の近似可能性について」(PDF)。博士論文、数値解析および計算科学部門、王立工科大学、ストックホルム{{citation}}: CS1 メンテナンス: 追記 (リンク)。
Klasing, Ralf; Laforest, Christian (2004)、「グラフにおける k 組支配の困難性結果と近似アルゴリズム」、Information Processing Letters、89 (2): 75–83、doi :10.1016/j.ipl.2003.10.004。
Papadimitriou, Christos H.; Yannakakis, Mihailis (1991)、「最適化、近似、および複雑性クラス」、Journal of Computer and System Sciences、43 (3): 425–440、doi :10.1016/0022-0000(91)90023-X
Parekh, Abhay K. (1991)、「グラフ内の小さな支配集合を見つけるための貪欲なヒューリスティックの分析」、Information Processing Letters、39 (5): 237–240、doi :10.1016/0020-0190(91)90021-9、hdl : 1721.1/1201
Raz, R. ; Safra, S. (1997)、「NP のサブ定数エラー確率低次テストとサブ定数エラー確率 PCP 特性」、Proc. 29th Annual ACM Symposium on Theory of Computing、ACM、pp. 475–484、doi :10.1145/258533.258641、ISBN 0-89791-888-6、S2CID 15457604。
高見沢健;西関剛; 斉藤暢 (1982)、「直列並列グラフ上の組合せ問題の線形時間計算可能性」、Journal of the ACM、29 (3): 623–641、doi : 10.1145/322326.322328、S2CID 16082154。
Telle, Jan Arne; Villanger, Yngve (2012)、「バイクリークフリーグラフにおける支配のための FPT アルゴリズム」、Epstein, Leah、Ferragina, Paolo (編)、アルゴリズム – ESA 2012: 第 20 回欧州シンポジウム、スロベニア、リュブリャナ、2012 年 9 月 10 ～ 12 日、議事録、Lecture Notes in Computer Science、vol. 7501、Springer、pp. 802 ～ 812、doi :10.1007/978-3-642-33090-2_69、ISBN 978-3-642-33089-6。
ヴァン・ローイ、JMM。ネダーロフ、J. van Dijk、TC (2009)、「包含/除外と測定と征服の組み合わせ: 支配的なセットをカウントするための正確なアルゴリズム」、Proc.第 17 回アルゴリズムに関する欧州年次シンポジウム、ESA 2009、コンピュータサイエンスの講義ノート、vol. 5757、Springer、pp. 554–565、doi :10.1007/978-3-642-04128-0_50、ISBN 978-3-642-04127-3。

さらに読む

Grandoni, F. (2006)、「最小支配集合の複雑さに関する注記」、Journal of Discrete Algorithms、4 (2): 209–214、CiteSeerX 10.1.1.108.3223、doi :10.1016/j.jda.2005.03.002。
Guha, S.; Khuller, S. (1998)、「連結支配集合の近似アルゴリズム」(PDF)、Algorithmica、20 (4): 374–387、doi :10.1007/PL00009201、hdl : 1903/830、S2CID 1249122。
ヘインズ、テレサ W. ; ヘデトニエミ、スティーブン; スレーター、ピーター (1998a)、『グラフにおける支配の基礎』、マルセル・デッカー、ISBN 0-8247-0033-3、OCLC 37903553。
ヘインズ、テレサ W. ; ヘデトニエミ、スティーブン; スレーター、ピーター (1998b)、グラフにおける支配: 高度なトピック、マルセルデッカー、ISBN 0-8247-0034-1、OCLC 38201061。
ウェスト、ダグラス B. (2001)、グラフ理論入門(第 2 版)、ピアソン教育。

[FOOTNOTEGareyJohnson1979-1] ギャリー＆ジョンソン（1979年）。

[FOOTNOTEWest2001Section_3.1-2] West（2001）、セクション3.1。

[FOOTNOTEKlasingLaforest2004-3] Klasing & Laforest (2004).

[FOOTNOTEFörster2013-4] フォルスター（2013年）。

[:0-5] Meshulam, Roy (2003-05-01). 「支配数とホモロジー」. Journal of Combinatorial Theory, Series A. 102 ( 2): 321–330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165.

[FOOTNOTEAllanLaskar1978-6] アラン＆ラスカー（1978年）。

[FOOTNOTEFaudreeFlandrinRyjáček1997-7] Faudree、Flandrin、Ryjáček（1997年）。

[:1-8] アハロニ、ロン;バーガー、イーライ。ジヴ、ラン (2007-05-01)。「加重グラフにおける代表者の独立したシステム」。コンビナトリカ。27 (3): 253–267。土井：10.1007/s00493-007-2086-y。ISSN 1439-6912。S2CID 43510417。

[FOOTNOTEHedetniemiLaskar1990-9] ヘデトニエミ＆ラスカー（1990）。

[FOOTNOTEKann1992108–109-10] Kann (1992)、108–109 ページ。

[FOOTNOTEEscoffierPaschos2006-11] エスコフィエ＆パスコス（2006年）。

[FOOTNOTERazSafra1997-12] ラズ＆サフラ（1997年）。

[FOOTNOTEParekh1991-13] パレック（1991年）。

[FOOTNOTEPapadimitriouYannakakis1991-14] パパディミトリウとヤナカキス (1991)。

[FOOTNOTECrescenziKannHalldórssonKarpinski2000-15] クレセンツィ他（2000年）。

[FOOTNOTETakamizawaNishizekiSaito1982-16] 高見沢・西関・斉藤 (1982).

[FOOTNOTEFominGrandoniPyatkinStepanov2008-17] フォミンら（2008年）。

[FOOTNOTEAlberFellowsNiedermeier2004-18] アルバー、フェローズ、ニーダーマイヤー (2004)。

[FOOTNOTEFominThilikos2006-19] フォミン＆ティリコス（2006年）。

[FOOTNOTETelleVillanger2012-20] テル＆ヴィランジェ（2012年）。

[FOOTNOTEDehneFellowsFernauPrieto2006-21] デーンら（2006年）。