申込締切
【対面を含むご参加の場合】2023年2月6日(月) 正午まで． 2023年2月17日(金) 正午まで．

【オンラインのみのご参加・ご欠席の場合】2023年2月17日(金) 正午まで．

 

発表者が学生時代から十数年来取り組んでいる分散計算理論がどのような分野であるのか，最近の研究事例2つを通してご紹介いたします．具体的には，
 (i) 個体群モデルにおけるリーダ選挙問題，および，
 (ii) モバイルエージェントによるビザンチン集合問題
について，問題設定やこれまでに発見されたいくつかのアルゴリズムをご解説いたします．

 

個体群モデルとは，消極移動（自分で制御できない移動）を絶えず行う微小で計算資源に乏しい計算機で構成するネットワークを表現する分散計算のモデルです．このモデルは2004年にAngluinらによって提案されて以来，盛んに研究が行われてきました．とりわけ，リーダ選挙問題と多数決問題のふたつは大変良く研究されている問題で，前者については，2020年にBerenbrinkらによってついに時間最適かつ空間最適なアルゴリズムが発見されました．本講演では，このリーダ選挙問題について解説します．

 

モバイルエージェントとは，計算機ネットワーク上を自律的に移動するソフトウェアのことです．ネットワーク上に存在するすべてのエージェントをひとつの計算機に集める集合問題は基本的かつ重要な問題で，分散計算理論のコミュニティでは大変よく研究されています．本講演では，ネットワーク上の一部のエージェントが任意の敵対的な行動を取る場合にも正常なエージェントをひとつの計算機に集合させることを目的としたビザンチン集合問題を紹介します．
 

k彩色遷移問題とは，無向グラフとその２つのk頂点彩色が与えられた際に，片方の彩色からもう片方の彩色へ，k頂点彩色であることを保ったまま，一度に一つの頂点の色を変えながら遷移することが可能であるか否かを判定する問題である．本講演では，ある色からある色へは直接変えることが出来ないという遷移可能性制約を考える．この制約は色を頂点とし，直接変えることのできる色の順序対を辺とする有向グラフにより与えることができる．本講演では，この有向グラフが有向サイクルであるかマルチツリーのある部分クラスに含まれる場合に，k彩色遷移問題が線形時間で解けることを示す．本講演は，藤井宗一郎氏，岩政勇仁氏，鈴木顕氏との共同研究に基づく．

オンライン二部マッチング問題は，二部グラフの片側の頂点がひとつずつやってくるときに，できるだけ大きなサイズのマッチングを求める問題である．この問題は検索広告の割り当て，ライドシェアリング，クラウドソーシングなどさまざまな応用をもつ．本講演では，オンライン二部マッチングに，これらの応用を動機とした制約を課した問題を考え，定数競合比を達成するアルゴリズムを提案する．本講演は，澄田範奈氏，伊藤伸志氏，竹村慧氏，波多野大督氏，福永拓郎氏，河原林健一氏との共同研究に基づく．

本講演では，学術変革(B)B01班で開発中の組合せ遷移問題を解くPythonライブラリを紹介する．reconfillion（仮）は部分グラフ列挙ライブラリである graphillion を基にして様々な組合せ遷移問題を解くライブラリであり，graphillion で表現可能な対象に関する組合せ遷移問題を解くことが可能である．reconfillion の中で用いられているアルゴリズムも紹介する．

各々が目的地をもつ複数エージェントをスムーズに移動させる技術はファクトリーオートメーションやビデオゲーム，ドローンショーなど，多方面に魅力的な応用がある．本講演ではグラフ上のエージェント群に衝突のない経路を割当てるマルチエージェント経路計画（Multi-Agent Path Finding; MAPF）を中心に，連続空間でのプランニングやロボット群での実行手法を取扱い, 移動エージェント群の制御手法を概観する．

有限な離散集合上に定義される統計モデルの当てはまりを評価するための，マルコフ連鎖を利用したシミュレーション手法を紹介する．既約なマルコフ連鎖を構成するための推移基底（マルコフ基底）は代数的に特徴づけられ，多項式環のグレブナー基底の理論を用いて計算することができる．本講演では，この問題を理解するために必要な統計学と代数学の理論を概説し，講演者の関連する研究を紹介する．

グラフが与えられたとき，その部分グラフを列挙する問題は計算機科学における基本的な問題である．部分グラフの数は入力グラフのサイズに対して指数的に大きくなりうるため，全ての部分グラフを1個ずつ出力するのは実用的でない場合がある．そこで我々は暗黙的部分グラフ列挙に注目する．暗黙的部分グラフ列挙では，部分グラフを陽に列挙する代わりに部分グラフの集合を表す決定グラフ（DD）を構築する．本講演ではDDを用いた暗黙的部分グラフ列挙に関する最近の研究を紹介する．

分散システムとは，相互に通信しながら協調して動作する多数の計算主体が作りだすシステムである．個々の計算主体はシステム全体の状況を把握できず，局所的，非同期的，並列的に計算や通信を行う．本講演の前半では，分散システムの通信グラフ上に構成した離散構造の遷移問題を紹介する．近年，独立点集合 [ICALP2019]，頂点彩色 [DISC2018]，全域木 [SSS2021]の分散遷移問題が異なる設定の下で提案されており，これらの結果を紹介する．講演の後半では，モバイルロボットやエージェントなどの自律的に計算，移動を行うモバイル計算主体群が構成する分散システムの遷移問題を紹介する．このような分散システムでは，計算主体の幾何的な配置に着目し，パターン形成問題や再構成問題という名前で遷移可能性が議論されてきた．講演者は近年，遷移列の繰返しや組合せによって探索や脱出といった機能を実現する研究に取り組んでいる．講演後半ではモバイルロボット群のパターン形成問題，モジュールロボットの探索と脱出を紹介する．

本発表では，各点が接続する辺に対する選好を持つ二部グラフ上のマッチング問題を考える．特に，安定性とパレート効率性と呼ばれる二つの性質を満たすマッチングであるパレート安定マッチングに対するアルゴリズムを考える．本発表では，講演者の最近の成果を含め，パレート安定マッチングに関する成果を，組合せ遷移的な視点も交えながら紹介する．

本講演では，組合せ遷移の産業応用について，配電網を例に紹介する．配電網は冗長性を持たせるために複数の経路で電気を供給できるように設計されてる．例えば配電網の日本標準モデルはネットワーク構成に約10^{58}個の選択肢がある．その中から最適な供給経路を選び出すだけでも難しい問題であるが，例え最適な供給経路を計算できたとしても，今度は途中で停電が起きないように現在の構成を最適な構成に変更するための切替手順が必要になる．本講演では，配電網の損失の最適化と切替手順を同時に求めるアルゴリズムの紹介，及びその実験結果について説明する．また，より実用を意識した問題設定である最適化遷移についても触れる．

現実世界の問題を解決する一般的手法のひとつとして，問題を数理的にモデリングし，そのモデルに対して最適化アルゴリズムを適用するという方法がある．このような文脈においては，最適化アルゴリズムはひとつの (近似) 最適解を求めることが一般的である．しかしながら，このような数理的モデルは現実世界を正確には反映できておらず，モデルの上でひとつの最適解を得ても，現実世界の問題の解決につながるとは限らない．（近似）最適解を複数求めて，その中から実問題に適するものを選ぶことが考えられるが，一般にそのような解は類似していることが多く，このような目的にはあまり意味をなさない．このような現実世界の問題と数理モデルとの間のギャップを解消するために，複数の「多様な」解を求める研究が行われている．本講演では，組合せ最適化問題における「多様な解」を発見するための最近の取り組みについて紹介する．

本講演は標的集合と呼ばれるグラフの頂点集合の性質にまつわる遷移問題を扱う．まず，各頂点vに閾値τ(v)の割り当てられたグラフ上で次の決定的な活性化過程を考える：非活性な頂点vは，τ(v)以上の近傍頂点が活性化していたら自身も活性化し，以後非活性化しない．ある頂点集合Sの頂点のみを最初に活性化した時に，最終的に残りの頂点全てが活性化する場合，Sを「標的集合」と呼ぶ．標的集合は適当なτ(v)の下で頂点被覆・フィードバック頂点集合に対応する．また，この活性化過程はネットワーク上のある種の拡散現象を捉えているため，グラフの最小標的集合を見つける最適化問題は，バイラルマーケティングや分散コンピューティング等の動機づけが与えられている．発表者は，標的集合の遷移問題として，ある標的集合から別の標的集合に，標的集合である性質を保ちながらToken Jump操作（頂点を一つずつ交換）の列の適用で遷移できるか否かを問う判定問題を考え，その計算量解析の結果を紹介する．一般の標的集合遷移問題のPSPACE困難性は頂点被覆遷移問題の結果から直ちに示されるため，入力グラフのクラスを制限した時の容易性・困難性を解析する．特に，次数・閾値の制限時にPとPSPACE困難のどちらに属するかの境界線を探索し，また，入力グラフが木の場合に多項式時間で解けることを示す．最後に計算量が未知のクラスを紹介したい．

多くの日本人は，小さい頃，あみだくじを使った記憶があるのではないだろうか．あみだくじは日本人にとって馴染み深いだけでなく，数学ならびに計算機科学において興味深い研究対象として認知されている．本講演では，あみだくじの列挙問題および遷移問題を紹介し，得られた結果を紹介する．はじめに，本講演で扱うあみだくじの定義を与える．続いて，あみだくじの列挙問題に対する結果として，発表者らが設計した列挙アルゴリズムの概要を解説する．このアルゴリズムは，あみだくじのブレイドリレーションという関係を利用することで列挙を行っている．続いて，あみだくじの遷移問題について解説する．2つのあみだくじが与えられたとき，一方のあみだくじからもう一方のあみだくじへ，ブレイドリレーションという関係を繰り返し用いることにより遷移可能かどうか，という遷移問題について，主に，最短の遷移長に関して得られた結果を解説する．

理論計算機科学の研究の中で，ゲームやパズルの研究は重要な役割を果たしてきた．特に計算量クラスの研究において，チューリング機械による特徴付けは必ずしもわかりやすいものではなく，特定の計算量クラスに対して直観的にわかりやすい単純な完全問題を示すことは，その計算量クラスに対する新たな視点と本質的な理解をもたらしてくれる．

　歴史的に見れば，特にクラスNPに関する完全問題が数多く示されたことにより，ある種のパズルの特徴がクラスNPを特徴づけていることが明らかになってきた．近年のコンピュータの発達とアルゴリズムの発展により，かなり大規模なNP完全問題が現実的な時間で解けるようになってきた背景には，こうした理解が進んだことも一定の役割を果たしているだろう．

　一方，歴史の中で50年近くも困難性が未解決だったパズルの一群が存在する．近年，こうしたパズルが組合せ遷移の枠組みで説明できることが徐々にわかってきた．特に，典型的なパズルがどれもPSPACE完全性を示していることは興味深い．組合せ遷移問題の枠組みでPSPACE完全性をもつ単純な問題を解明していくことは，クラスPSPACEの構造の理解が進展することが期待され，今後，ある程度のPSPACE完全問題を現実的な時間で解けるようになる．

　最後にいくつかの組合せ遷移の観点から興味深い未解決問題をいくつか共有したい．

グラフの向き付けとは，無向グラフの各辺に向きを付けて有向グラフを得ることをいい，組合せ最適化やグラフ理論の分野で盛んに研究されているトピックである．本講演では，連結度制約を保ちながら向き付けの辺の向きを1本ずつ変更していく，「グラフ向き付けの遷移」に関する講演者らの最新の成果について紹介する．我々の主結果は，「2k辺連結無向グラフの任意の向き付けに対して，うまく辺の向きを1本ずつ変更していくことで辺連結度を単調に増加させ，最終的にk辺連結向き付けを得ることができる」というものである．これは，古典的な Nash-Williams の定理を強めた結果であり，k辺連結向き付けのフリップ・グラフの連結性を議論する際にも有用である．

なお，この成果は本プロジェクトメンバーとの共同研究に基づくものであり，SODA2022で発表予定である．

トークンスライディング問題（TS問題）は組合せ遷移において最もよく研究されている問題のひとつである．本講演ではこの問題の有向グラフ版である有向トークンスライディング問題（有向TS問題）を考える．TS問題ではトークンを辺の向きに沿ってどちら向きにも動かせるが，有向TS問題ではトークンを辺の向きに沿ってしか動かせないという非対称性がある．無向辺は逆向きの2つの有向辺で模倣できるため，有向TS問題はTS問題の一般化である．本講演では，有向TS問題に対して，グラフクラスを限定した場合の困難性を示す．また，主結果として，入力が木を向き付けたグラフの場合に多項式時間で解けることを示す．本講演の内容はA01班，C01班のメンバーと大学院生を含む共同研究に基づく．