Research on algorithms for domination and covering of large-scale graphs

本研究はグラフの支配問題や被覆問題について，その最適解の性質を数理的に解明したり，最適解や近似解を求めるアルゴリズムを設計することを目標としている。さらに，高速に最適解に近い解を求めるヒューリスティクスを設計することを第２の目標としている。2022年度は，グラフの安全支配集合に対する理論的な研究を主に行った。得られた成果は主に以下の2点である。（１）外平面グラフにおける安全支配集合のシャープな上界と下界を証明した。外平面グラフの頂点数をパラメータとして，最適な安全支配集合のサイズの上界と下界を示すことができた。（２）プロパーインターバルグラフの最適な安全支配集合を決定する線形時間アルゴリズムを設計した。同じグラフに対するアルゴリズムはすでに開発されているが，そのアルゴリズムには誤りが含まれていたため，新たに設計し正しい証明を与えたものである。これらの成果は国際誌に投稿しAcceptとなっている。（（１）の成果は，採録となった論文誌で掲載される号が来年度になる。）安全支配集合問題は，構造が単純なグラフでも多項式時間アルゴリズムを設計することが，複雑になることが経験的に分かってきた。本研究の成果によって，研究者が同種の問題の新たなアルゴリズムを設計する動機づけとなることを期待している。また，関連する問題として，極大平面グラフにおける完全独立全域木の構成について考察し，その成果を発表することができた。これは既知の成果を広げるものである。成果としては，まだ未解決な部分が多く，目標とするものに及ばないものであるため，今後も継続して研究を行う。

本研究はグラフの支配問題や被覆問題について，その最適解の性質を数理的に解明したり，最適解や近似解を求めるアルゴリズムを設計することを目標としている。さらに，高速に最適解に近い解を求めるヒューリスティクスを設計することを第２の目標としている。2022年度は，グラフの安全支配集合に対する理論的な研究を主に行った。得られた成果は主に以下の2点である。（１）外平面グラフにおける安全支配集合のシャープな上界と下界を証明した。外平面グラフの頂点数をパラメータとして，最適な安全支配集合のサイズの上界と下界を示すことができた。（２）プロパーインターバルグラフの最適な安全支配集合を決定する線形時間アルゴリズムを設計した。同じグラフに対するアルゴリズムはすでに開発されているが，そのアルゴリズムには誤りが含まれていたため，新たに設計し正しい証明を与えたものである。これらの成果は国際誌に投稿しAcceptとなっている。（（１）の成果は，採録となった論文誌で掲載される号が来年度になる。）安全支配集合問題は，構造が単純なグラフでも多項式時間アルゴリズムを設計することが，複雑になることが経験的に分かってきた。本研究の成果によって，研究者が同種の問題の新たなアルゴリズムを設計する動機づけとなることを期待している。また，関連する問題として，極大平面グラフにおける完全独立全域木の構成について考察し，その成果を発表することができた。これは既知の成果を広げるものである。成果としては，まだ未解決な部分が多く，目標とするものに及ばないものであるため，今後も継続して研究を行う。