Proper Circular Arc Graph における最小安全支配集合問題
下西希実

1(指導教員：長尾篤樹)

はじめに警備員の配置場所等のモデル化として最小安全支配集合問題が考えられている。この問題は NP 完全ではあるが、Proper Interval Graph に関しては線形時間アルゴリズムが存在することが知られている。[1] 本研究
では Proper Circular Arc Graph においても最小安全支配集合が多項式時間で解けることを証明する。

2

図 1 Proper Circular Arc Graph の例

安全支配集合問題

頂点数 n の無向グラフ G = (V, E) について、集合D ⊆ V は、各 u ∈ V \ D がある v ∈ D に隣接するとき、D は G の支配集合である。Proper Circular Arc
Graph では O(n) で求められるとわかっている。[2]
G の支配集合 S ⊆ V は各 u ∈ V \ S について、隣接する v ∈ S との交代集合 (S \ {v}) ∪ {u} が再び G の支配集合となるとき、S は G の安全支配集合である。このとき v は u を守るという。[3]2.1

図2

3.2

既存研究

Proof. 全 て の i = 1, 2, ..., k に つ い て xi ≤ ti ≤maxN (xi ) であり、yi ∈ N [xi ] である。すなわち、xi はyi から ti の全ての頂点に隣接する。また、yi = (ti−1 )+であるので、y1 ≤ yk であるとき、tk−1 が y1 の左隣またはそれより右側となるので G の全ての頂点は S の頂点に隣接する。

Theorem 2. アルゴリズム 1 で得られる集合 S は安全支配集合である。

Proper Circular Arc Graph におけるProof. Lemma 1 より X が G 全体を守るためには
y1 ≤ yk であれば良い。x1 ≤ xk ならば y1 ≤ yk であることを示す。（xk のみ二周目のものとする。）(1) xk = maxN (yk ) の場合
x1 = maxN (y1 ) で x1 ≤ xk つまり maxN (y1 ) ≤maxN (yk ) G は Proper Circular Arc Graph なのでy1 ≤ yk(2) xk = maxN (maxN (yk−1 )+ ) の場合+maxN (yk−1 ) < tk−1 よ っ て maxN (yk−1) < ykyk < y1 と す る と xk = maxN (maxN (yk−1 )+ ) <maxN (y1 ) となり、xk ≤ x1 であることに矛盾。よって仮定が否定され、y1 ≤ yk安全支配集合問題
3.1

提案アルゴリズム本節では、Proper Circular Arc Graph における安全支配集合問題を解くアルゴリズムを提案する。付録にある本アルゴリズムは Proper Circular Arc Graph のある頂点を v1 と指定したのちに本問題を解く。以下、本アルゴリズムの正当性を証明する。
Lemma 1. y1 ≤ yk ならば S = {xi , ..., xk−1 } は G 全体を守る。（yk のみ二周目のものとする。
）

Proper Interval Graph とは、区間グラフのうち、ある区間の真部分集合になるような区間が存在しない区間グラフである。頂点数 n の Proper Interval Graph の左端の頂点を v1 とし、右向きに順に v1 , v2 , ..., vn とする。
vi の隣接頂点を N [vi ] と表す。全ての i について N [vi ]が連続、つまり、ある i1 , i2 に対して N [vi ] = {vt |i1 ≤t ≤ i2 } となるとき、グラフ G の頂点 (v1 , ..., vn ) はConsecutive Ordering を持つという。またこのとき、隣接頂点 N [vi ] のうち最大のものを maxN (vi ) と表す。
グラフ G が consecutive ordering を持つとき、グラフG は proper interval graph である。[4] これを利用し、Proper Interval Graph における最小安全支配集合問題
は O(|V (G)|) で求められることが証明されている。[1]3頂点番号 6 を v1 としてアルゴリズム 1 を適用したもの。y4 は二周目の頂点番号 6 となっている。

Proper Circular Arc Graph

Proper Circular Arc Graph とは区間が円弧上になった Proper Interval Graph である。区間を頂点とみなし、ある区間に対し、その始点を含む区間を左側の区間(頂点) と呼び、その終点を含む区間を右側の区間 (頂点)と呼ぶ。この定義の下で、ある頂点を v1 と決めたなら、各頂点は時計周りを右向きと見なして順に v1 , v2 , ..., vnと呼ぶことができ、consecutive ordering となる。これ
により、maxN (vi ) は vi の隣接頂点のうち、最も右側にあるものとする。さらに、i > j に対し、N [vi ] が vjを vi の右側に含むとき、その vj を二周目の vj と呼ぶ。
安全支配集合 S の要素を {x1 , ..., xk }, xi が守る左端の頂点を yi , 右端の頂点を ti とする。頂点の位置関係を≤ で表現し、vi ≤ vj は i ≤ j を表す。さらに、vi+ をvi の右側にある頂点で一番左側にあるものとする。

Lemma 3. 頂点 u を開始頂点としてアルゴリズム 1を適用した際に得られる SDS Su と、頂点 v を開始頂点としてアルゴリズム 1 を適用した際に得られる SDSSv を考える。このとき、Su における x1 と Sv における x1 とが同じ頂点を指す場合、Su = Sv である。
Proof. x1 = t1 = maxN (y1 ) より、y1 から t1 はク+リーク。y2 = t+1 で、x2 = maxN (y2 ) = maxN (x1 ).

1

maxN (yl ) かつ vn ≤ tl であることを示す。Lemma 5より、sl−1 は yl を守らないので、yl は sl に守られている。よって、(Su \ {sl }) ∪ {yl } は支配集合。yl は xl に′隣接し、xl は vn を守っているので、vn ≤ maxN (yl )sl ≤ xl ≤ vn ≤ maxN (yl ) より sl は vn に隣接するので、xl は vn と隣接。つまり、vn ≤ maxN (xl ) 以下、x1 から x2 がクリークかどうかは y1 に依らない。クリークならば t2 = maxN (x2 ), クリークでないならば
t2 = maxN (maxN (x1 )+ ) よって、x1 が決まれば、y1の位置に関わらず、y2 , x2 , t2 が一意に定まり、i > 2 でも i − 1 の頂点のみで yi , xi , ti が定まる。x1 ≤ xk が成り立てば停止するので、Su = Sv = {x1 , ..., xk−1 } 全て同じ要素となる。したがって、Su と Sv で x1 が同じ頂点を指す場合、Su = Sv

アルゴリズムの挙動により場合分けをする。

(1) xl = maxN (yl ) の場合
vn ≤ maxN (xl ) = tl となるので k = l である。
(2) xl = maxN (maxN (yl−1 )+ ) の場合
Su は 安 全 支 配 集 合 な の で 、sl は vn を 守 る 。よ っ′て 、Sl = (Su \ {sl }) ∪ {vn } は 支 配 集 合 。s =′maxN (sl−1 )+ とする。Sl は支配集合で、s は sl−1′と隣接しないので、s は vn と隣接する。つまり、vn ≤′maxN (s ) したがって、tl = maxN (maxN (xl−1 )+ ) ≥′maxN (maxN (sl−1 )+ ) ≥ maxN (s ) ≥ vn
以上より、vn ≤ maxN (yl ) かつ vn ≤ tl が成り立+つ。yl+1 = t+l ≥ vn = v1 , xl+1 = maxN (yl+1 ) ≥maxN (v1 ) = x1 と な り 、x1 ≤ xl+1 が 成 り 立 ち 、
i = l + 1 の時、アルゴリズム 1 の while 文が終了するため、k = l である。

Lemma 4. Proper Circular Arc Graph に お け る
SDS Su に対し、ある頂点 u ∈ Su が G に含まれるどの極大なクリークにも右端の頂点ではないとする。
この時、u を含む一番左に存在する極大なクリークをCu とし、その右端の頂点を v とすると、Su ∪ {v} \ {u}もまた、SDS である。

Proof. u と隣接する左端の頂点はクリーク Cu の左端の頂点である。右端の頂点は maxN (u) である。u が守る頂点の範囲は最大で Cu の左端の頂点から maxN (u)である。v もクリーク Cu 内の頂点なので、v と隣接する左端の頂点は変わらない。u < v より maxN (u) ≤maxN (v) なので v と隣接する右端の頂点は u と隣接する右端の頂点よりも手前には存在しない。したがって、Cu の右端の頂点 v は u と入れ替えても守ることのできる頂点の範囲は減ることはない。よって (Su ∪{v})\{u}
もまた、G における SDS である。

Theorem 7. Proper Circular Arc Graph G に対し、O(|V (G)|2 ) 時間で最小安全支配集合を出力するアルゴリズムが存在する。

Proof. アルゴリズム 1 は O(|V (G)|) で実行可能である。また、x1 となる頂点の候補から開始頂点を限定し た と き 、最 大 で も |V (G)| 回 実 行 す れ ば 良 い の でO(|V (G)|2 ) で求めることができる。

G における全ての頂点が何かしらの極大なクリークの右端の頂点となっている任意の最小安全支配集
合 Su = {s1 , ..., sl } に対し、x1 = s1 となる条件からアルゴリズム 1 を実行して得られる安全支配集合を
S = {x1 , ..., xk } とする。この時、v1 = y1 , vn+ = v1 とする。このとき、アルゴリズムより si ≤ xi が言え、さらに以下の補題が成り立つ。

4

まとめと今後の課題

本研究では Proper Circular Arc Graph における最小安全支配集合問題が多項式時間で解けることを示した。今後の課題について、計算量を線形時間に減らせないか、関連問題である Total Dominating Set 問題等
も Proper Circular Arc Graph に限定することで多項式時間で解けるかということが考えられる。

Lemma 5. i ≥ 2 について、1 ≤ j ≤ i − 1 に対して、sj は yj+1 を守らない。
Proof. j ∈ {2, 3, ..., i − 1} に対して、sj が yj+1 を守′ると仮定する。つまり、sj が yj+1 に隣接し、Su =(Su \ {sj }) ∪ {yj+1 } が支配集合であると仮定する。sjは yj+1 に隣接するため yj+1 ≤ maxN (sj ) であり、さらに仮定より sj ≤ xj ≤ tj < yj+1 である。以下、アルゴリズムの挙動により場合分けをする。
(1) tj = maxN (xj ) の場合+yj+1 = t+j = maxN (xj ) である。sj が yj+1 を守るとすると、yj+1 ≤ maxN (sj ) ≤ maxN (xj ) = tj となり矛盾。
(2) tj = maxN (maxN (xj−1 )+ ) の場合w = maxN (xj−1 )+ と す る 。yj+1 = t+=jmaxN (w)+ であるので、w は yj+1 と隣接しない。また、w > maxN (xj−1 ) ≥ maxN (sj−1 ) なので、sj−1 は′w と隣接しない。よって、Su = (Su \ {si }) ∪ {yj+1 })の中に w と隣接する点はない。よって矛盾。

参考文献[1] Toru Araki and Hiroka Miyazaki. Secure domination in proper interval graphs. Discrete Applied
Mathematics, Vol. 247, pp. 70–76, 2018.
[2] Wen-Lian Hsu and Kuo-Hui Tsai. Linear timealgorithms on circular-arc graphs. Information
Processing Letters, Vol. 40, No. 3, pp. 123–129,
1991.
[3] E.J. Cockayne, P.J.P. Grobler, W.R. Grundlingh,
J. Munganga, and J.H. Van Vuuren. Protectionof a graph. Utilitas Mathematica, Vol. 67, p. 19 –32, 2005.
[4] Peter J. Looges and Stephan Olariu. Optimal
greedy algorithms for indiﬀerence graphs. Computers & Mathematics with Applications, Vol. 25,
No. 7, pp. 15–25, 1993.

Theorem 6. X は G の最小安全支配集合である。
Proof. k = l を示す。つまり、アルゴリズム 1 の while
文が i = l + 1 の時に停止することを示す。これを示すために、x1 ≤ xl+1 であることを示す。まず、vn ≤2付録
Algorithm 1 提案アルゴリズム
Input: Proper Circular Arc Graph G, consecutive
ordering for V (G)Output: 最小安全支配集合 S
1: maxN (v1 ), ..., maxN (vn ) を計算
2: y1 ← v1 , x1 ← maxN (y1 ), t1 ← maxN (y1 )3: S ← {x1 }, i ← 1
4: while xi が二周目でない do
5:i ← i + 1, yi ← t+i−1

6:if maxN (yi−1 ) < ti−1 then

7:
8:
9:

xi = maxN (maxN (yi−1 )+ )else
xi = maxN (yi )10:

end if11:

if maxN (xi−1 ) < xi then

12:13:
14:ti = maxN (maxN (xi−1 )+ )else
ti = maxN (xi )15:

end if16:

S ← S ∪ {xi }17: end while
18: returnS \ {xi }3