自己紹介
氏名: 小林靖明 (こばやし やすあき)
所属・職位: 情報知識ネットワーク研究室・准教授
研究分野:・アルゴリズムと計算量の理論研究スタイル:・(どちらかといえば) 理論より・研究は楽しく，(自分に) 厳しく・わかるまで，考えよう
小林の研究や研究指導について質問があればkoba at ist.hokudai.ac.jp
へ連絡してください1

研究分野 (一覧)
計算困難な問題に対する理論研究と応用

グラフの描画疎グラフの最大カット
対称疎行列の掃き出し法

グラフの分解

固定パラメータ容易性，組合せ順序に関する実験的研究
最適化，近似アルゴリズム，列挙アルゴリズム，計算量理論，離散数学，グラフ理論，数理論
理，(整数)線形計画法, etc.
(+プログラミング)
木の間の距離を計算

述語論理を用いた組合せ遷移のメタ定理

組合せ遷移(状態変化に対応するアルゴリズム)に関する研究「多様な解」を複数見つける

AI分野におけるアルゴリズムの理論・実用研究2

研究分野 (一覧)
計算困難な問題に対する理論研究と応用あるひとつテーマについて研究しているというよりも，(問題を解くための) 新しい道具を作ったり，グラフの描画
疎グラフの最大カット
既存の道具を拡張したりすることに興味があります

対称疎行列の掃き出し法

グラフの分解

固定パラメータ容易性，組合せ順序に関する実験的研究
最適化，近似アルゴリズム，列挙アルゴリズム，計算量理論，
離散数学，グラフ理論，数理論
理，(整数)線形計画法, etc.
(+プログラミング)
木の間の距離を計算

述語論理を用いた組合せ遷移のメタ定理

組合せ遷移(状態変化に対応するアルゴリズム)に関する研究「多様な解」を複数見つける

AI分野におけるアルゴリズムの理論・実用研究

3

研究分野 (一覧)
計算困難な問題に対する理論研究と応用あるひとつテーマについて研究しているというよりも，(問題を解くための) 新しい道具を作ったり，グラフの描画
疎グラフの最大カット
既存の道具を拡張したりすることに興味があります

対称疎行列の掃き出し法

固定パラメータ容易性，組合せ順序に関する実験的研究
最適化，近似アルゴリズム，列挙アルゴリズム，計算量理論，離散数学，グラフ理論，数理論
理，(整数)線形計画法, etc.
理論研究の魅力(個人的意見)(+プログラミング)
木の間の距離を計算
グラフの分解既存の研究よりも (何らかの意味で) 優れていることを数学的に証明できる！

述語論理を用いた組合せ遷移のメタ定理

組合せ遷移(状態変化に対応するアルゴリズム)に関する研究「多様な解」を複数見つける

AI分野におけるアルゴリズムの理論・実用研究

4

学生の研究 その1 (修士)
・始点と終点が指定された枝重み付き有向グラフの中から，𝑘 本の最短経路でできるだけ「遠い」ものを見つける
スタート

・「遠さ」を対ごとのハミング距離としたときに，その最小値の最大化問題に対して効率的なアルゴリズムを開発­ 固定パラメータ容易性5

学生の研究 その2 (学士)
・グラフの中からできるだけ少ない頂点を選んで，「羨み」の無い施設配置を行う
任意の頂点について，そこから選ばれた頂点の距離を考えたとき，最も近い頂点の中に同じ色の頂点が存在・グラフが (𝑛 頂点の) 木の場合 & 頂点が2色で塗られて居る
ときの 𝑂 𝑛! 時間アルゴリズム [Dey+, FCT 2021]
・それとは異なるアイデアを用いて(定数) 𝑘 色の場合でも実行可能な多項式時間アルゴリズムを開発
・国際会議 WAAC 2023 で発表済み
6

研究の進め方
・学生自身がやりたいテーマを考える-> 小林の専門と合えば指導できますが，そうじゃない場合は一緒に勉強していく (学生自身が主体的に研究を進める必要あり)．

・テーマは与えてほしいが，研究の方向性は自分で決めたい-> アルゴリズムや計算量の理論研究ならば小林の専門なので，やりたいことの方向性に沿ってアドバイスすることはできます．
-> そうじゃない場合でも，研究の方向性を一緒に勉強していきます．

・テーマを考えるのも，方向性を決めるのも思いつかない-> 主にグラフを対象としたアルゴリズムや計算量の理論研究のテーマをいくつか提示して，興味が惹かれるテーマに取り組んでもらいます．
-> 自分で新たな課題を発見するということは身につかないかもしれませんが，どのようなことが最先端の研究で行われていて，しっかり論理的に議論ができて，証明をかけるようになれば，立派な研究です．
7

研究の進め方
・学生自身がやりたいテーマを考える-> 小林の専門と合えば指導できますが，そうじゃない場合は一緒に勉強していく (学生自身が主体的に研究を進める必要あり)．
数学やプログラミングに優れている必要はありませんが，数学を使った (英語の) 論文をじっくり読んだり，・テーマは与えてほしいが，研究の方向性は自分で決めたい
他者と数学的な議論をすることが要求されると思います．

-> アルゴリズムや計算量の理論研究ならば小林の専門なので，やりたいことの方向性に沿ってアドバイスすることはできます．
-> そうじゃない場合でも，研究の方向性を一緒に勉強していきます．

・テーマを考えるのも，方向性を決めるのも思いつかない-> 主にグラフを対象としたアルゴリズムや計算量の理論研究のテーマをいくつか提示して，興味が惹かれるテーマに取り組んでもらいます．
-> 自分で新たな課題を発見するということは身につかないかもしれませんが，どのようなことが最先端の研究で行われていて，しっかり論理的に議論ができて，証明をかけるようになれば，立派な研究です．
8

研究の進め方
・学生自身がやりたいテーマを考える-> 小林の専門と合えば指導できますが，そうじゃない場合は一緒に勉強していく (学生自身が主体的に研究を進める必要あり)．
数学やプログラミングに優れている必要はありませんが，数学を使った (英語の) 論文をじっくり読んだり，・テーマは与えてほしいが，研究の方向性は自分で決めたい
他者と数学的な議論をすることが要求されると思います．

-> アルゴリズムや計算量の理論研究ならば小林の専門なので，やりたいことの方向性に沿ってアドバイスすることはできます．
-> そうじゃない場合でも，研究の方向性を一緒に勉強していく．

・テーマを考えるのも，方向性を決めるのも思いつかない-> 主にグラフを対象としたアルゴリズムや計算量の理論研究のテーマをいろいろなことを勉強して「問題を解く」のが好きなので，いくつか提示して，興味 が惹かれるテーマに取り組んでもらいます．
せっかくなのでその達成感を味わってもらいたいです．
-> 自分で新たな課題を発見するということは身につかないかもしれませ
そして，世界一の結果を出して，んが，どのようなことが最先端の研究で行われていて，しっかり論理国際会議で発表しましょう！
的に議論ができて，証明をかけるようになれば，立派な研究です．
9

(参考) 研究分野 (一覧) の詳細グラフの描画
・グラフをできるだけ「見やすく」描画する­「見やすさ」を「辺交差数が少ない」と定義

・一般にはNP困難だが，最適な描画における辺の交差数が少ない場合に高速に動作するアルゴリズムを与えた
辺の交差が少ないほど見やすいYasuaki Kobayashi, Hisao Tamaki: A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization.
Algorithmica, 72(3), 778-790, 2015
Yasuaki Kobayashi, Hisao Tamaki: A faster fixed parameter algorithm for two-layer crossing minimization. Information Processing Letters,
116(9), 547-549, 2016.
Yasuaki Kobayashi, Hiromu Ohtsuka, Hisao Tamaki: An improved fixed-parameter algorithm for one-page crossing minimization.
In Proc. of IPEC 2017, LIPICS, vol. 89, 25:1-25:12, 201710

(参考) 研究分野 (一覧) の詳細
グラフの分解・グラフを「うまく」分解すると様々な問題が効率良く解ける
・そのような分解を見つけるアルゴリズムを与えたグラフの最適消去木の計算
グラフのパス分解の計算

ZDDの変数順序の計算に応用
Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki,
Toshihiro Tano: Computing directed pathwidthin O(1.89n) time. Algorithmica, 75(1), 138-157, 2016
小林靖明，中畑裕: 線形枝幅を計算する厳密アルゴリズムとフロンティア法への応用. 人工知能学会 第110回SIGFPAI
2019

Yasuaki Kobayashi, Hisao Tamaki: Treedepth parameterized
by vertex cover number. In Proc. of IPEC 2016, LIPICS, vol. 63,
18:1-18:11, 20162012年に作ったアルゴリズム．
現在も世界で一番速い．

11(参考) 研究分野 (一覧) の詳細
グラフの最大カット
・古典的な組合せ最適化問題である最大カット問題の研究
・一般的にはNP困難であることが知られている・平面グラフ (平面に辺交差なしで描画可能なグラフ)に対する多項式時間を，少交差グラフへ拡張することに成功
1970年代の結果の拡張

少交差グラフの最大カット
Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru
Tamaki: An improved fixed-parameter algorithm for max-cut
parameterized by crossing number. In Proc of IWOCA 2019, LNCS,
vol. 11638, 327-338, 2019

最適2等分割Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone: A (probably)
optimal algorithm for Bisection on bounded-treewidthgraphs. Theoretical Computer Science 873, 38-46, 2021

12(参考) 研究分野 (一覧) の詳細
NP困難な問題に対する実験的研究
・対称行列の掃き出し法の最適順序を求めるアルゴリズム
・根付き木同士の編集距離を計算するアルゴリズム­ 文字列ではO(n2)で計算できるが，(無順序) 木ではNP困難­ 効率の良い整数計画法の定式化を提案
整数計画法ソルバを使った研究
国際会議に併設された
aaaa
プログラミ
cdcdb c dc c d
ングコンテストで優勝
c dc dfcafa
対称疎行列の掃き出し法
順序に関する実験的研究
小林靖明，玉木久夫: 最小フィルイン問題に対する安全なセパレータ．
情報処理学会研究報告，第164回アルゴリズム研究会，京都，2017

afff

木の編集距離Eunpyeong Hong, Yasuaki Kobayashi, Akihiro Yamamoto: Improved
Methods for Computing Distances between Unordered Trees Using
Integer Programming. In Proc. of COCOA 2017, LNCS, vol. 10628,
pp. 45-60, 201713

(参考) 研究分野 (一覧) の詳細
組合せ遷移問題の研究
・与えられたふたつの「構造」を少しずつ変化させて「遷移」させるアルゴリズムの研究
・数理論理を用いたアルゴリズム的メタ定理を提案
実行時間が (初等的関数で)書き下せないほど大きい！

述語論理を用いた組合せ遷移のメタ定理
Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi:
Algorithmic Meta-Theorems for Combinatorial Reconfiguration
Revisited. ESA 2022, LIPIcs, vol. 244, 61:1-61:15, 2022

マトロイド理論と関連する技法を用いる

有向木の遷移Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota
Otachi, Kunihiro Wasa: Reconfiguring Directed Trees in a Digraph. InProc. of COCOON 2021, LNCS, vol. 13025, pp. 343-354, 2021

14

(参考) 研究分野 (一覧) の詳細多様な解を見つけるアルゴリズム
・組合せ最適化問題において，ひとつの最適解を求めることは多項式時間で可能­ 最短路問題: ダイクストラ法­ 最小全域木: クラスカルのアルゴリズム­ 2部グラフの最大マッチング: ホップクロフト・カープのアルゴリズム

・複数の多様な解を求めるアルゴリズムを提案
Color-codingと呼ばれる技法を用いる

多様な解発見フレームワーク
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota
Otachi: Finding Diverse Trees, Paths, and More. In Proc.
of AAAI 2021, 35(5), 3778-3786, 2021

最小費用流やマトロイドなどを使う

多様な最短路Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee,
Yota Otachi: Computing Diverse Shortest Paths Efficiently: A
Theoretical and Experimental Study. AAAI 2022, 36(4), 3758-3766,
2022

15