2021年度

• 伊藤 健洋（東北大学, 領域代表）が，国際会議The 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022) にて，招待講演を行います．

   

  2022年3月25日(金)
  Takehiro Ito
  "Invitation to Combinatorial Reconfiguration"

   

  WALCOM2022は，3月24日(木)ー26日(土)の開催です．一般の査読付き国際会議ではありますが，第1セッションは Combinatorial Reconfiguration と名付けられました．A01班の研究成果も発表します．

   

  2022年3月24日(木)
  Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, and Kunihiro Wasa
  "Reconfiguration of Regular Induced Subgraphs"

  オンライン参加は無料です．
  参加お申込みは，WALCOM 2022のWebサイトをご覧ください．

  2022.03.24 Thu. -26 Sat.

  国際会議WALCOM 2022にて招待講演
  話者： 題目： 概要：伊藤 健洋（東北大学, 領域代表）が，国際会議The 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022) にて，招待講演を行います．   2022年3月25日(金) Takehiro Ito "Invitation to Combinatorial Reconfiguration"   WALCOM2022は，3月24日(木)ー26日(土)の開催です．一般の査読付き国際会議ではありますが，第1セッションは Combinatorial Reconfiguration と名付けられました．A01班の研究成果も発表します．   2022年3月24日(木) Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, and Kunihiro Wasa "Reconfiguration of Regular Induced Subgraphs" オンライン参加は無料です． 参加お申込みは，WALCOM 2022のWebサイトをご覧ください．

  • 公開イベント
  • 2021年度

• 予定：	9:25～9:30	オープニング
  	9:30～12:00	学生シンポジウム（午前の部）
  	12:00～13:00	お昼休憩
  	13:00～15:40	学生シンポジウム（午後の部）
  	16:00～17:00	本研究領域の活動について（公開）
  	（18:00～	オンライン懇談会）

   

  プログラムの詳細は，こちらのPDF版 をご覧ください．

   

  • 発表予定（◎は発表者）

  9:30-9:50 ◎ 岡⽥ 優⽃ (名古屋⼤学)，⽊⾕ 裕紀 (九州⼤学)，⼤舘 陽太，⼩野 廣隆 (名古屋⼤学) グラフ上の⾊付きドロップ順次交換の計算量 9:50-10:10 ◎ ⻘池 宥希 (横浜市⽴⼤学)，清⾒ 礼 (成蹊⼤学)，⼩林 靖明(京都⼤学)，⼤舘 陽太 (名古屋⼤学) 置換グラフ上の最⼤独⽴集合遷移問題の多項式時間解法 10:10-10:30 ◎ 前⽥ 陽平，川原 純 (京都⼤学) 制約を緩和したトークンスライディング問題 10:40-11:00 ◎ 柳澤 佑介，鈴⽊ 顕，⽥村 祐⾺，周 暁 (東北⼤学) グラフ彩⾊の最適化遷移問題について 11:00-11:20 ◎ 市野 達也，川原 純，湊 真⼀ (京都⼤学) 彩⾊遷移ソルバーの実装と性能 11:20-11:40 ◎ ⼩⻄ 岳志，川原 純 (京都⼤学)，⼾⽥ 貴久 (電気通信⼤学) 有界モデル検査による全域⽊遷移ソルバ実装⼿法の提案と評価 11:40-12:00 ◎ 荻野 奨太，池辺 淑⼦，鮏川 矩義 (東京理科⼤学) 船の到着時刻の不確実性を考慮したコンテナ整列問題 13:00-13:20 ⼟井 義燿 (酒⽥市⽴第⼆中学校)，今野 紀雄 (横浜国⽴⼤学)，中上川 友樹 (湘南⼯科⼤学)，佐久間 雅 (⼭形⼤学)，瀬川 悦⽣(横浜国⽴⼤学)，篠原 英裕 (所属なし)，⽥村 駿也 (横浜国⽴⼤学)，◎⽥中 優帆 (東北⼤学)，豊⽥ 晃典 (⼭形⼤学) サイクルの⼆乗グラフ上の乱歩における期待到達時間の解析 13:20-13:40 ◎ 檜 拓磨，仲⽥ 研登 (岡⼭⼤学) グレイシャー対応の⼀般化について 13:40-14:00 ◎ 伊藤 ⼤修，⼭中 克久，平⼭ 貴司 (岩⼿⼤学)，⼩林 靖明 (京都⼤学) 線形拡張の遷移問題に関する研究 14:00-14:20 ◎ 堤 幸太朗，佐野 良夫，久野 誉⼈ (筑波⼤学) Hom-complexの連結性判定問題に対する組合せ遷移 14:40-15:00 ◎ 重信 賢直，神⼭ 直之，⽊村 慧 (九州⼤学) 多項式時間可解なHorn ILS及びTVPI ILSにおける遷移問題の拡 張に関する研究 15:00-15:20 ◎ 鎌⽥ ⽃南，上原 隆平 (JAIST) 多⾯体の間の再折り遷移問題の研究 15:20-15:40 ◎ 平林 可意，藤原 洋志，⼭本 博章 (信州⼤学) ビンパッキング問題の遷移問題に関する研究

   

   

  2022.03.09 Wed.

  2021年度「組合せ遷移」の学生シンポジウム
  話者： 題目： 概要： 予定： 9:25～9:30 オープニング   9:30～12:00 学生シンポジウム（午前の部）   12:00～13:00 お昼休憩   13:00～15:40 学生シンポジウム（午後の部）   16:00～17:00 本研究領域の活動について（公開）   （18:00～ オンライン懇談会）   プログラムの詳細は，こちらのPDF版 をご覧ください．   発表予定（◎は発表者） 9:30-9:50 ◎ 岡⽥ 優⽃ (名古屋⼤学)，⽊⾕ 裕紀 (九州⼤学)，⼤舘 陽太，⼩野 廣隆 (名古屋⼤学) グラフ上の⾊付きドロップ順次交換の計算量 9:50-10:10 ◎ ⻘池 宥希 (横浜市⽴⼤学)，清⾒ 礼 (成蹊⼤学)，⼩林 靖明(京都⼤学)，⼤舘 陽太 (名古屋⼤学) 置換グラフ上の最⼤独⽴集合遷移問題の多項式時間解法 10:10-10:30 ◎ 前⽥ 陽平，川原 純 (京都⼤学) 制約を緩和したトークンスライディング問題 10:40-11:00 ◎ 柳澤 佑介，鈴⽊ 顕，⽥村 祐⾺，周 暁 (東北⼤学) グラフ彩⾊の最適化遷移問題について 11:00-11:20 ◎ 市野 達也，川原 純，湊 真⼀ (京都⼤学) 彩⾊遷移ソルバーの実装と性能 11:20-11:40 ◎ ⼩⻄ 岳志，川原 純 (京都⼤学)，⼾⽥ 貴久 (電気通信⼤学) 有界モデル検査による全域⽊遷移ソルバ実装⼿法の提案と評価 11:40-12:00 ◎ 荻野 奨太，池辺 淑⼦，鮏川 矩義 (東京理科⼤学) 船の到着時刻の不確実性を考慮したコンテナ整列問題 13:00-13:20 ⼟井 義燿 (酒⽥市⽴第⼆中学校)，今野 紀雄 (横浜国⽴⼤学)，中上川 友樹 (湘南⼯科⼤学)，佐久間 雅 (⼭形⼤学)，瀬川 悦⽣(横浜国⽴⼤学)，篠原 英裕 (所属なし)，⽥村 駿也 (横浜国⽴⼤学)，◎⽥中 優帆 (東北⼤学)，豊⽥ 晃典 (⼭形⼤学) サイクルの⼆乗グラフ上の乱歩における期待到達時間の解析 13:20-13:40 ◎ 檜 拓磨，仲⽥ 研登 (岡⼭⼤学) グレイシャー対応の⼀般化について 13:40-14:00 ◎ 伊藤 ⼤修，⼭中 克久，平⼭ 貴司 (岩⼿⼤学)，⼩林 靖明 (京都⼤学) 線形拡張の遷移問題に関する研究 14:00-14:20 ◎ 堤 幸太朗，佐野 良夫，久野 誉⼈ (筑波⼤学) Hom-complexの連結性判定問題に対する組合せ遷移 14:40-15:00 ◎ 重信 賢直，神⼭ 直之，⽊村 慧 (九州⼤学) 多項式時間可解なHorn ILS及びTVPI ILSにおける遷移問題の拡 張に関する研究 15:00-15:20 ◎ 鎌⽥ ⽃南，上原 隆平 (JAIST) 多⾯体の間の再折り遷移問題の研究 15:20-15:40 ◎ 平林 可意，藤原 洋志，⼭本 博章 (信州⼤学) ビンパッキング問題の遷移問題に関する研究    

  • 公開イベント
  • 2021年度
• 小林 佑輔 (京都大学，C01班) が，電子情報通信学会コンピュテーション研究会にて，C01班の研究成果に関して招待講演を行います．

   

  2022年3月6日 (日) 13:30-14:30

  Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto and Kenta Ozeki,
  Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

  (SODA 2022 採択論文)

   

  参加お申込みは，研究会のWebサイトをご覧ください．

  電子情報通信学会コンピュテーション研究会

   

  2022.03.06 Sun.

  電子情報通信学会コンピュテーション研究会にて招待講演
  話者： 題目： 概要：小林 佑輔 (京都大学，C01班) が，電子情報通信学会コンピュテーション研究会にて，C01班の研究成果に関して招待講演を行います．   2022年3月6日 (日) 13:30-14:30 Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto and Kenta Ozeki, Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams (SODA 2022 採択論文)   参加お申込みは，研究会のWebサイトをご覧ください． 電子情報通信学会コンピュテーション研究会  

  • 公開イベント
  • 2021年度
  • C01
• 伊藤 健洋 (東北大学, 領域代表）が，情報処理学会主催のIPSJ-ONEにて講演を行います．

  情報処理学会アルゴリズム研究会からの推薦を受けて講演するものです．

   

  2022年3月5日 (土) 15:30 - 17:30
  伊藤 健洋「組合せ遷移のアルゴリズム理論 ―パズル・ゲームから配電制御まで―」

   

  聴講方法など詳細は，こちらのWebサイトをご覧ください．

  https://ipsj-one.org/

  2022.03.05 Sat.

  IPSJ-ONEにて講演
  話者： 題目： 概要：伊藤 健洋 (東北大学, 領域代表）が，情報処理学会主催のIPSJ-ONEにて講演を行います． 情報処理学会アルゴリズム研究会からの推薦を受けて講演するものです．   2022年3月5日 (土) 15:30 - 17:30 伊藤 健洋「組合せ遷移のアルゴリズム理論 ―パズル・ゲームから配電制御まで―」   聴講方法など詳細は，こちらのWebサイトをご覧ください． https://ipsj-one.org/

  • 公開イベント
  • 2021年度
• 和佐 州洋 (豊橋技術科学大学，A01班) が，人工知能学会 第119回人工知能基本問題研究会 (SIG-FPAI) にて招待講演を行います．

   

  2022年1月28日 (金) 11:00 - 12:00
  和佐 州洋 (豊橋科学技術大学, A01班）「難しい列挙問題に対するアプローチ」

   

  参加お申込みは，研究会のWebサイトをご覧ください．

  第119回人工知能基本問題研究会

   

  2022.01.28 Fri.

  第119回人工知能基本問題研究会にて招待講演
  話者： 題目： 概要：和佐 州洋 (豊橋技術科学大学，A01班) が，人工知能学会 第119回人工知能基本問題研究会 (SIG-FPAI) にて招待講演を行います．   2022年1月28日 (金) 11:00 - 12:00 和佐 州洋 (豊橋科学技術大学, A01班）「難しい列挙問題に対するアプローチ」   参加お申込みは，研究会のWebサイトをご覧ください． 第119回人工知能基本問題研究会  

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

  2022.01.20 Thu. 10:00-12:00

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

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

  2022.01.06 Thu. 10:00-12:00

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

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

  2021.12.16 Thu. 10:00-12:00

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

  • セミナー
  • 2021年度
• 2021.11.29 Mon.

  Workshop "Graph Theory for Combinatorial Reconfiguration"
  話者： 題目： 概要：

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

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

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

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

  2021.11.25 Thu. 10:00-12:00

  第18回セミナー・勉強会
  話者：上原 隆平（北陸先端科学技術大学院大学，招待講演） 題目：組合せ遷移問題の視点から見たパズルの歴史 概要： 理論計算機科学の研究の中で，ゲームやパズルの研究は重要な役割を果たしてきた．特に計算量クラスの研究において，チューリング機械による特徴付けは必ずしもわかりやすいものではなく，特定の計算量クラスに対して直観的にわかりやすい単純な完全問題を示すことは，その計算量クラスに対する新たな視点と本質的な理解をもたらしてくれる． 　歴史的に見れば，特にクラスNPに関する完全問題が数多く示されたことにより，ある種のパズルの特徴がクラスNPを特徴づけていることが明らかになってきた．近年のコンピュータの発達とアルゴリズムの発展により，かなり大規模なNP完全問題が現実的な時間で解けるようになってきた背景には，こうした理解が進んだことも一定の役割を果たしているだろう． 　一方，歴史の中で50年近くも困難性が未解決だったパズルの一群が存在する．近年，こうしたパズルが組合せ遷移の枠組みで説明できることが徐々にわかってきた．特に，典型的なパズルがどれもPSPACE完全性を示していることは興味深い．組合せ遷移問題の枠組みでPSPACE完全性をもつ単純な問題を解明していくことは，クラスPSPACEの構造の理解が進展することが期待され，今後，ある程度のPSPACE完全問題を現実的な時間で解けるようになる． 　最後にいくつかの組合せ遷移の観点から興味深い未解決問題をいくつか共有したい．

  • セミナー
  • 2021年度