日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-A-10

コーダルグラフ上での最小 dynamic monopoly 問題に対する多項式時間アルゴリズム
申請中
05000191

筑波大学 *松崎 照央
筑波大学 佐野 良夫

概要

1.

口コミでのマーケティングや、病気の感染など、拡散する過程をグラフ上でモデル化した概念として、dynamic monopoly と呼ばれる概念がある [4]。
dynamic monopoly の問題として、グラフ G と各頂点 v に対する閾値 τ (v) が与えられたとき、最小サイズの dynamic monopoly を見つける問題（別名：target set selection）がある。この問題は一般には NP 困難であり、閾値 τ (v) を定数としてもNP 困難である。さらに、様々なグラフクラスで計算量の解析が行われており、閾値 τ (v) を定数として扱う場合は、木や区間グラフなどのグラフクラスでは多項式時間で解けることがわかっている[2, 5]。また、木幅が w のグラフでは nO(w) 時間で解ける [1]。一方、スプリットグラフなどのグラフクラスでは NP 困難である [2]。しかし、その間にあるコーダルグラフについては、τ ≤ 2 の場合に多項式時間で解けることはわかっていたが、任意の定数 t に対して τ ≤ t の場合に多項式時間で解けるかは未解決だった [3]。本研究では、これまでの研究で扱われてきた動的計画法を発展させ、コーダルグラフに対する多項式時間アルゴリズムを与える。

MATSUZAKI Akio
SANO Yoshio

また、この線形順序 ≺ を dynamic monopoly
S の cascade と呼ぶ。(G, τ ) の最小の dynamicmonopoly のサイズを dyn(G, τ ) と表す。

2.2.

コーダルグラフグラフ G に対し、G の長さ 4 以上の閉路を取ってきたとき、閉路の 2 頂点を接続するその閉路を構成しない辺があるようなグラフをコーダルグラ
フという。

2.3.

部分木の交差グラフ

集合族 S = {S1 , . . . , Sn } に対して、

V (G) = {v1 , . . . , vn }E(G) = {{vi , vj } | i ̸= j, Si ∩ Sj ̸= ∅}で定義されるグラフ G を S の交差グラフと呼ぶ。
コーダルグラフは木の部分木の族の交差グラフとして表現できる [6]。また、木ではなく二分木の交差グラフとしても表現できる。図 1 にコーダルグ
ラフとその交差グラフ表現を示す。

AB

CF
G

準備

2.
2.1.

D

dynamic monopoly

無向グラフ G = (V, E) と各頂点 v に対する閾値
τ (v) が与えられたとき、頂点集合 S ⊆ V に対して、τ (v) 個以上 S に属する頂点に隣接する頂点 vを S に加える操作を繰り返すことで S = V となる
とき、S を (G, τ ) の dynamic monopoly という。
つまり、(G, τ ) の頂点集合 S に対して、条件∀v ∈ V − S, |{u ∈ NG (v) : u ≺ v}| ≥ τ (v)を満たす V の線形順序 ≺ が存在するとき、S を(G, τ ) の dynamic monopoly という。

EHA B
CB FGCBECD E

BG
EEGH

図 1: コーダルグラフとその交差グラフ表現

3.

主結果

補題 3.2.

定理 3.1. t を定数とする。閾値が高々t であるコーダルグラフ (G, τ ) に対する最小 dynamic monopoly
問題は多項式時間で解ける。
証明はコーダルグラフを根付き二分木の部分木の交差グラフとして見ることで、動的計画法を構成した。交差グラフ表現の根付き木と部分木の族を (T, {T (v)}v∈V (G) ) として Tx を x を根とした Tの部分木としたとき、

Ux := {u ∈ V (G) | x ∈ V (T (u))}∪UTx :=Uyy∈V (Tx )と定義する。コーダルグラフ G を、各 x ∈ V (T ) に対し次の 4 つの条件のいずれかが成り立つような根が r である二分木 T の交差グラフとして表現し、(i) x の子は 2 つ（y, y ′ とする）で、Ux = Uy =Uy′(ii) x の子は 1 つ（y とする）で、Ux ⊂ Uy かつ|Uy \ Ux | = 1(iii) x の子は 1 つ（y とする）で、Uy ⊂ Ux かつ|Ux \ Uy | = 1(iv) x の子はない (x は T の葉である)x ∈ V (T ) に対し、(Unodes , Udyn , ≺, σ) を• Udyn ⊆ Unodes ⊆ Ux , |Unodes | = min{|Ux |, t}• ≺: 「u ∈ Udyn , v ∈ Unodes \ Udyn ⇒ u ≺ v 」
を満たす Unodes の全順序
• σ : Unodes → [t]の組とし、τ ′ : V (G) → Z≥0 を{σ(v) v ∈ Unodes のとき
τ ′ (v) :=τ (v) それ以外とする。OPTx (Unodes , Udyn , ≺, σ) を• W ⊆ UTx \ Ux
• W ∪ Udyn が (UTx , τ ′ ) := (G[UTx ], τ ′ |UTx ) のdynamic monopoly である。
• W ∪ Udyn の G[UTx ] 上での cascade ≺′ で、– ≺′ は ≺ の UTx への線形拡張– u ∈ Unodes , v ∈ Ux \ Unodes ⇒ u ≺′ vとなるようなものが存在する。という条件を満たす最小の頂点集合 W のサイズと定義する。

dyn(G, τ ) = OPTr (∅, ∅, ∅, σ)である。
補題 3.3.

OPTx (Unodes , Udyn , ≺, σ)は、x の子 y それぞれに対してすべての′′OPTy (Unodes, Udyn, ≺′ , σ ′ )がわかっている、または、x が葉であるとき、多項式時間で計算できる。
これらの補題を示すことで、定理 3.1 が証明される。

参考文献[1] Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, and Ilan Newman. Treewidth governs the complexity of target set selection.
Discrete Optimization, 8(1):87–96, 2011.
[2] Stéphane Bessy, Stefan Ehard, Lucia D.
Penso, and Dieter Rautenbach. Dynamicmonopolies for interval graphs with boundedthresholds. Discrete Applied Mathematics,
260:256–261, 2019.
[3] Chun-Ying Chiang, Liang-Hao Huang, BoJr Li, Jiaojiao Wu, and Hong-Gwa Yeh.
Some results on the target set selection problem. Journal of Combinatorial Optimization,
25:702–715, 2011.
[4] Pedro Domingos and Matt Richardson. Mining the network value of customers. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discoveryand Data Mining, KDD ’01, page 57–66. Association for Computing Machinery, 2001.
[5] Mitre C. Dourado, Stefan Ehard, Lucia D.
Penso, and Dieter Rautenbach. Partial immunization of trees. Discrete Optimization,
35:100568, 2020.
[6] Fǎnicǎ Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs.
Journal of Combinatorial Theory, Series B,
16(1):47–56, 1974.