二部立方体グラフにおける最大幸福集合問題
足立有香 (指導教員：長尾篤樹)

1の頂点を持つものを考える. n は偶数であり, G の最小二等分幅が b であるとする. そこで, MaxHS のインスタンスペアとなる二部立方体グラフ G′ = (V ′ , E ′ ) と整数 k を構成する. V (G) = {v1 , v2 , ..., vn }(n は偶数) とすると, グラフ G′ は n 個の頂点 v1 から vn に対応する
n 個の部分グラフ G′1 = (V1 , E1 ) から G′n = (Vn′ , En′ )によって構成される. 各 i ∈ {1, 2, ..., n} に対して G′iの頂点集合を i 番目の頂点ガジェットと呼ぶこととする. i 番目の頂点ガジェットは, Vi = {vi,1 , vi,2 , vi,3 } ∪∪n′′′{vi,1, vi,2, vi,3} ∪ j=1 {Ui,1,j ∪ Ui,2,j ∪ Ui,3,j } である.
ここで, 各 Ui,1,j , Ui,2,j , Ui,3,j は図 1 のようにそれぞれn 本のパスと 3 個の頂点から構成される. G′i は 9n + 6個の頂点を二部性を保ちながら持つことが分かる. これらの頂点ガジェットに対し, G 上に辺 (vi , vj ) が存在するとき, またその時に限り, G′i と G′j の次数 2 の頂点が二部性を保ちつつ図 2 のように辺を追加する. G′ の頂点総数は (9n + 6) × n = 9n2 + 6n であることが分かる. ここで k = (9n2 + 6n)/2 とする. 以上のアルゴリズムを利用し, 以下の定理を証明する.

はじめにグラフはネットワーク構造を表現することができ, 例
えば大学内での友人関係や企業間の取引関係といった社会ネットワークを表す際に用いられる. これらの社会ネットワークを表現するグラフは人物や企業等を頂点とし, それら同士の関係を辺として表している. この社会ネットワークにおける同類性から, 最大幸福集合問
題 (MaxHS) が「頂点部分集合問題」として定式化された.[1] MaxHS は, 二部グラフや立方体グラフにおいてNP 困難であることが先行研究で証明されている. 本研
究では, 二部立方体グラフや r ≥ 4 である二部 r-正則グラフに制限してもなお MaxHS が NP 困難であることの証明を行った.

2

数学的準備

本章では, 最大幸福集合問題 (MaxHS) と, 二部立方体グラフや二部 r-正則グラフにおける MaxHS の NP
困難性の証明に必要な最小二等分問題を紹介する.

2.1

最大幸福集合問題 (MaxHS)

無向グラフ G = (V, E) とその頂点集合 S ⊆ V に対して, 頂点 v とその隣接頂点が S にあれば幸福, そうでなければ不幸であるという. ここで, S に含まれる幸福な頂点の個数を #h(S) と表記する.
Deﬁnition 1. 最大幸福集合問題 (MaxHS) は以下のように定義される.
入力：無向グラフ G = (V, E) および整数 k
出力：#h(S) が最大となるような k 個の部分集合

S⊆V
MaxHS はブロックグラフや区間グラフ, 木幅が一定になるグラフにおいて多項式時間アルゴリズムが示されている一方で, 二部グラフや立方体グラフは NP 困難であることが証明されている.[2]2.2

図1最小二等分問題|V | = 2n の無向グラフ G = (V, E) 上の |S| = n となるようなカット (S, V \ S) が含む辺の本数を S の二等分幅という.
Deﬁnition 2. 最小二等分問題は以下のように定義される.
入力：|V | = 2n の無向グラフ G = (V, E)
出力：二等分幅が最小のカット (S, V \ S)
偶数頂点の r-正則グラフにおける最小二等分問題は任意の整数 r ≥ 3 に対して NP 困難であることが知られている.[3]3i 番目の頂点ガジェット G′i

図2

G から G′ への帰着

Theorem 3. 二部立方体グラフにおける MaxHS はNP 困難である.
Proof. 上 述 の ア ル ゴ リ ズ ム が 最 小 二 等 分 問 題 か ら
MaxHS への多項式時間帰着であることを証明する.
このアルゴリズムは O(n2 ) 時間で G′ を出力する. 以下では, G の最小二等分幅が最大 b のとき, かつそのときに限り, G′ に k = (9n2 + 6n)/2 個の頂点を持つ集合
S ′ ⊆ V ′ が存在し, S ′ における幸福な頂点の個数が少な
くとも #h(S ′ ) = (9n2 + 6n)/2 − 2b であることを示す.
十分条件は, 最小二分割問題の解の存在性より自明にMaxHS の解の存在が導かれるため明らかである.

二部立方体グラフにおける MaxHS

本章では先行研究の立方体グラフにおける MaxHSの NP 困難性の証明 [2] を用い, 二部立方体グラフ (すなわち二部性を持つ 3-正則グラフ) に制限してもなおMaxHS が NP 困難であることを示す.
帰着のために以下のアルゴリズムを考える. 最小二等分問題の入力である立方体グラフ G で |V (G)| = n 個1能であることを示す. 入力グラフである r-正則グラフ
G = (V, E) から MaxHS のインスタンスペアとなる
二部 r-正則グラフ G′ = (V ′ , E ′ ) と整数 k を構成する. V (G) = {v1 , v2 , ..., vn }(n は偶数) とすると, グラ
フ G′ は n 個の頂点 v1 から vn に対応する n 個の部分グラフ G′1 = (V1 , E1 ) から Gn = (Vn , En ) によって構成される. 各 i ∈ {1, 2, ..., n} に対して G′i の頂点′′′集合は Vi = {vi,1 , vi,2 , ..., vi,r } ∪ {vi,1, vi,2, ..., vi,r}∪′′′{wi,1 , wi,2 , ..., wi,r } ∪ {wi,1 , wi,2 , ..., wi,r } である. 図 4のように, G′i は 4r 個の頂点で構成され, 二部性を持つことが分かる. これを r-正則グラフ G 上の辺 (vi , vj )を G′i と G′j の次数 2 の頂点が二部性を保つように接続する. G′ の頂点総数は 4rn であることが分かる. ここで k = 2rn とする. G の最小二等分幅が b のとき, G′の最小二等分幅は 2b である. この帰着は多項式時間で行うことができる. 以上のアルゴリズムと Theorem 3から以下の定理が示せる.

以下に必要条件を示す. すなわち, G の最小二等分幅が少なくとも b + 1 であるとするとき, 帰着グラ
フ G′ におけ る 頂点 数 k = (9n2 + 6n)/2 であ るような頂点集合 S ′ が持つ幸福な頂点の個数は最大で(9n2 + 6n)/2 − 2b − 1 であることを示す. ここで背理法のために, |Ŝ| ≤ k かつ #h(Ŝ) ≥ (9n2 + 6n)/2 − 2bでとなる集合 Ŝ が存在すると仮定する. 鳩の巣原理より Ŝ は x ≥ n/2 個の頂点ガジェットが少なくとも 1 個の頂点を持つことが言える.
x = n/2 個の頂点ガジェットを完全に含み, それ以外の頂点ガジェットは 1 個の頂点も含まないような頂点集合 S2 を考える. G の最小二等分幅が少なくともb + 1 であるという仮定から, G′ の最小二等分幅は少な
くとも 2(b + 1) = 2b + 2 である. よって, 少なくとも2b + 2 個の頂点は V ′ \ S2 に近傍を持つため不幸になる.
#h(S2 ) < (9n2 + 6n)/2 − 2b − 1 より, x ≥ n/2 + 1 個の頂点ガジェットは Ŝ に少なくとも 1 個の頂点を含むと考えられる.
以上より Ŝ は, S2 からある頂点集合 W ⊆ S2 を取り除いた上で, |W ′ | = |W | となるような W ′ ⊆ V ′ \ S2 を選び, それを S2 に追加した頂点集合であると考えることができる.

図4

二部 r-正則グラフの帰着ガジェット G′i の例

Theorem 5. r ≥ 3 である二部 r-正則グラフにおけるMaxHS は NP 困難である.
図35

S2 と Ŝ の関係

先行研究の立方体グラフにおける MaxHS の NP 困
難性の証明を用い, r ≥ 3 である二部 r-正則グラフに制限してもなお MaxHS が NP 困難であることを証明した. 今後の課題として, 二部立方体平面グラフや r ≥ 4の二部 r-正則平面グラフに制限を強めた場合はどうか,ということが挙げられる.

Lemma 4. S2 の不幸な頂点を幸福にするため, 例えば S2 の不幸な頂点の近傍 w ′ を V ′ \ S2 から Ŝ に追加することを考える. すると 1 個の頂点が幸福になる. しかしその分 1 個の頂点を Ŝ から削除しなければならな
くなる. 例えば S2 から幸福な頂点を取り除くとその近傍の 3 個の頂点が不幸になり, 不幸な頂点を取り除くとS2 に含まれる近傍 2 個の頂点が不幸になる.

参考文献[1] Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka,Guohui Lin, Eiji Miyano, and Ippei Terabaru. Parameterized algorithms for the happy set problem.
Discrete Applied Mathematics, Vol. 304, pp. 32–44, 2021.
[2] Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka,
Guohui Lin, Eiji Miyano, and Ippei Terabaru.
Complexity and approximability of the happy setproblem. Theoretical Computer Science, Vol. 866,
pp. 123–144, 2021.
[3] Thang Nguyen Bui,Soma Chaudhuri,Frank Thomson Leighton, and Michael Sipser.
Graph bisection algorithms with good averagecase behavior. Combinatorica, Vol. 7, No. 2, pp.
171–191, 1987.

Lemma 4 より, S2 の中の c 個の不幸な頂点を幸福にしようとすると, 頂点の集合 W ⊆ S2 を削除して少な
くとも c 個の頂点が不幸になることが分かる. これは#h(Ŝ) ≤ #h(S2 ) となり Ŝ の定義と矛盾する. 同様に任意の W と W ′ について Ŝ = (S2 \ W ) ∪ W ′ における幸福な頂点の個数は最大でも #h(S2 ) であることを示すことができる. したがって, G の最小二等分幅が少な
くとも b + 1 であるとするとき, G′ が k = (9n2 + 6n)/2個の部分集合 S ′ ⊆ V ′ を持ち, 幸福な頂点の数 #h(S ′ )が最大で (9n2 + 6)/2 − 2b − 1 であるといえる.

4

まとめと今後の課題

二部 r-正則グラフにおける MaxHS

本章では r ≥ 4 の二部 r-正則グラフでも同様に最小二等分問題から MaxHS へ多項式時間での帰着が可2