Organization
Faculty of Environmental, Life, Natural Science and Technology Associate Professor
Position
Associate Professor
External link
Kazuhiro Kurita
Degree
-
博士（情報科学） ( 2020.3 北海道大学 )
Research Interests
-
Optimization
-
Algorithm
-
Top-K/K-best enumeration
-
Enumeration
Education
-
Hokkaido University 大学院情報科学研究科 情報理工学
2017.4 - 2020.3
Country： Japan
Research History
-
Okayama University 大学院環境生命自然科学学域 Associate Professor
2025.10
Country：Japan
-
Nagoya University Graduate School of Informatics Assistant Professor
2022.7 - 2025.9
Country：Japan
-
National Institute of Informatics 情報学研究プリンシプル系
2020.4 - 2022.6
Country：Japan
-
Japan Society for the Promotion of Science
2019.4 - 2021.3
Country：Japan
Professional Memberships
-
一般社団法人人工知能学会
2021.6
-
一般社団法人情報処理学会
2020.5
Papers
-
Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size.
Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Davide Rucci, Takeaki Uno, Kunihiro Wasa
Algorithmica 87 ( 9 ) 1247 - 1273 2025.9
-
The Complexity of Maximal Common Subsequence Enumeration
Giovanni Buzzega, Alessio Conte, Yasuaki Kobayashi, Kazuhiro Kurita, Giulia Punzi
Proceedings of the ACM on Management of Data 2025.6
-
On the Complexity of Minimising the Moving Distance for Dispersing Objects.
Nicolás Honorato Droguett, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono 0001
CoRR abs/2502.12903 2025.2
-
Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Discrete Applied Mathematics 2025.1
-
Spanner Enumeration for Temporal Graphs.
Kazuhiro Kurita, Andrea Marino 0001, Jason Schoeters, Takeaki Uno
4th Symposium on Algorithmic Foundations of Dynamic Networks(SAND) 9 - 21 2025
-
Designing Output Sensitive Algorithms for Subgraph Enumeration.
Alessio Conte, Kazuhiro Kurita, Andrea Marino 0001, Giulia Punzi, Takeaki Uno, Kunihiro Wasa
From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday 19 - 40 2025
-
Space-Efficient FPT Algorithms for Degeneracy.
Naohito Matsumoto, Kazuhiro Kurita, Masashi Kiyomi
IEICE Transactions on Information & Systems 108 ( 3 ) 208 - 213 2025
-
On the Complexity of Minimising the Moving Distance for Dispersing Objects.
Nicolás Honorato Droguett, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono 0001
19th International Symposium on Algorithms and Data Structures(WADS) 36 - 14 2025
-
Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints.
Yasuaki Kobayashi, Kazuhiro Kurita, Kevin Mann, Yasuko Matsui, Hirotaka Ono 0001
Algorithms 18 ( 2 ) 112 - 112 2025
-
Polynomial-delay enumeration of large maximal common independent sets in two matroids and beyond.
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Inf. Comput. 304 105282 - 105282 2025
-
On the hardness of inclusion-wise minimal separators enumeration
Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, Kunihiro Wasa
Information Processing Letters 185 106469 - 106469 2024.3
-
On the complexity of finding a spanning even tree in a graph.
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Atsuki Nagao, Hirotaka Ono 0001, Kazuhisa Seto
CoRR abs/2412.17307 2024
-
Kazuhiro Kurita, Kunihiro Wasa
Theor. Comput. Sci. 1005 114628 - 114628 2024
-
Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints.
Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono 0001
IWOCA 232 - 246 2024
-
Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size.
Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Davide Rucci, Takeaki Uno, Kunihiro Wasa
CoRR abs/2405.13613 2024
-
Dichotomies for Tree Minor Containment with Structural Parameters
Tatsuya Gima, Soh Kumabe, Kazuhiro Kurita, Yuto Okada, Yota Otachi
WALCOM 1026 392 - 405 2024
-
要素数制約付き極小辺被覆の多項式遅延列挙
小林 靖明, 栗田 和宏
人工知能学会研究会資料 人工知能基本問題研究会 126 39 - 43 2023.11
-
Enumerating Empty and Surrounding Polygons.
Shunta Terui, Katsuhisa Yamanaka, Takashi Hirayama, Takashi Horiyama, Kazuhiro Kurita, Takeaki Uno
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 106 ( 9 ) 1082 - 1091 2023.9
-
Optimal LZ-End Parsing is Hard.
Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, Takeaki Uno
CoRR abs/2302.02586 2023
-
Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints.
Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono
CoRR abs/2308.16426 2023
-
Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids.
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
MFCS 58 - 14 2023
-
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Kazuhiro Kurita, Yota Otachi
AAAI 3968 - 3976 2023
-
Optimal LZ-End Parsing Is Hard.
Hideo Bannai, Mitsuru Funakoshi, Kazuhiro Kurita, Yuto Nakashima, Kazuhisa Seto, Takeaki Uno
CPM 3 - 11 2023
-
Kazuhiro Kurita, Kunihiro Wasa
CoRR abs/2201.08647 2022
-
Constant amortized time enumeration of Eulerian trails.
Kazuhiro Kurita, Kunihiro Wasa
Theor. Comput. Sci. 923 1 - 12 2022
-
Polynomial-Delay and Polynomial-Space Enumeration of Large Maximal Matchings.
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
WG 342 - 355 2022
-
Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study.
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota Otachi
AAAI 3758 - 3766 2022
-
Linear-Delay Enumeration for Minimal Steiner Problems.
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
PODS 301 - 313 2022
-
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion.
Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Kazuhiro Kurita, Yota Otachi
Theory Comput. Syst. 66 ( 2 ) 502 - 515 2022
-
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Kazuhiro Kurita, Yota Otachi
CoRR abs/2201.08940 2022
-
Efficient enumeration of dominating sets for sparse graphs Reviewed
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
Discrete Applied Mathematics 303 283 - 295 2021.11
-
A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number Reviewed
Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
Theoretical Computer Science 874 32 - 41 2021.5
-
Polynomial-Delay Enumeration of Large Maximal Matchings.
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
CoRR abs/2105.04146 2021
-
Finding Diverse Trees, Paths, and More. Reviewed
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi
The 35th AAAI Conference on Artificial Intelligence (AAAI 2021) 2021
-
Constant Amortized Time Enumeration of Eulerian trails.
Kazuhiro Kurita, Kunihiro Wasa
CoRR abs/2101.10473 2021
-
Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study.
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota Otachi
CoRR abs/2112.05403 2021
-
Finding the Anticover of a String. Reviewed
Mai Alzamel, Alessio Conte, Shuhei Denzumi, Roberto Grossi, Costas S. Iliopoulos, Kazuhiro Kurita, Kunihiro Wasa
31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) 161 2 - 11 2020
-
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
AOIKE Yuuki, GIMA Tatsuya, HANAKA Tesshu, KIYOMI Masashi, KOBAYASHI Yasuaki, KOBAYASHI Yusuke, KURITA Kazuhiro, OTACHI Yota
電子情報通信学会技術研究報告(Web) 120 ( 276(COMP2020 18-27) ) 2020
-
Polynomial Delay Enumeration for Minimal Steiner Problems
KOBAYASHI Yasuaki, KURITA Kazuhiro, WASA Kunihiro
電子情報通信学会技術研究報告(Web) 120 ( 209(COMP2020 11-17) ) 2020
-
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
CoRR abs/2009.08830 2020
-
Efficient Enumerations for Minimal Multicuts and Multiway Cuts. Reviewed
Kazuhiro Kurita, Yasuaki Kobayashi
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) 170 60 - 14 2020
-
Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number
栗田和宏, 和佐州洋, 宇野毅明, 有村博紀
電子情報通信学会技術研究報告 119 ( 249(COMP2019 18-28)(Web) ) 2019.11
-
An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Sparse Graphs. Reviewed
Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
Combinatorial Algorithms - 30th International Workshop(IWOCA) 339 - 351 2019
-
Efficient Enumeration of Dominating Sets for Sparse Graphs. Reviewed
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
29th International Symposium on Algorithms and Computation(ISAAC) 8 - 13 2018
-
Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four. Reviewed
Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 101-A ( 9 ) 1383 - 1391 2018
-
Efficient Enumeration of Subgraphs and Induced Subgraphs with Bounded Girth. Reviewed
Kazuhiro Kurita, Kunihiro Wasa, Alessio Conte, Takeaki Uno, Hiroki Arimura
Combinatorial Algorithms - 29th International Workshop(IWOCA) 201 - 213 2018
-
Listing Acyclic Subgraphs and Subgraphs of Bounded Girth in Directed Graphs. Reviewed
Alessio Conte, Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno
Combinatorial Optimization and Applications - 11th International Conference 169 - 181 2017
MISC
-
出力依存型DD構築の計算複雑性
栗田和宏
列挙アルゴリズムセミナー 2025.8
-
⾼さ2の根付き⽊に対する頻出飽和部分⽊の多項式遅延列挙
甲本健太, 栗田和宏, 小野廣隆
2025年度夏のLAシンポジウム 2025.7
-
ラベル付き木に対する極大頻出誘導部分木マイニングの計算複雑性
甲本健太, 栗田和宏, 小野廣隆
2025.3
-
有向ハイパーグラフ上のパスと極小頂点カットの列挙
栗田和宏, ケビンマン
2024年度冬のLAシンポジウム 2025.1
-
Maximal Common Subsequence Enumeration is Hard
Giovanni Buzzega, Alessio Conte, Yasuaki Kobayashi, ○Kazuhiro Kurita, Giulia Punzi
2025.1
-
Finding distinct 2-maximal independent sets is hard
Yasuaki Kobayashi, Kazuhiro Kurita
2025.1
-
コード類似を利用した楽曲の自然な変容
松下 昂世, 栗田 和宏, 小野 廣隆
2024年度冬のLAシンポジウム 2025.1
-
重み制約付き極大マッチングの多項式遅延列挙
小林靖明, 栗田和宏, 和佐州洋
列挙アルゴリズムセミナー 2024.8
-
Computing diverse pair of solutions for SAT
2024.3
-
Computing diverse pair of solutions for SAT
2024.2
-
An Edit Model and Algorithms for Achieving Properties on Intersection Graphs
オノラト ドロゲット ニコラス, 栗田 和宏, 土中 哲秀, 小野 廣隆
2023年度冬のLAシンポジウム 2024.2
-
極小シュタイナー多点対頂点カット列挙の計算困難性
小林 靖明, 栗田 和宏
2023年度冬のLAシンポジウム 2024
-
Algorithms for Optimally Shifting Intervals under Intersection Graph Models
Nicolás Honorato Drogue, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono
日本オペレーションズ・リサーチ学会 九州支部 九州地区におけるOR若手研究交流会 2023.10
-
最適 LZ-End 分解
坂内 英夫, 舩越 満, 栗田 和宏, 中島 祐人, 脊戸 和寿, 宇野 毅明
2022年度冬のLAシンポジウム 2023.2
-
弦グラフの部分クラスにおける極大誘導部分グラフ列挙への多項式遅延アルゴリズム
佐藤嶺, 小林靖明, 栗田和宏, 和佐州洋
電子情報通信学会技術研究報告(Web) 123 ( 325(COMP2023 16-27) ) 2023
-
Maximum Minimal k-Path Vertex Cover Problem
HANAKA Tesshu, KOBAYASHI Yasuaki, KURITA Kazuhiro
情報処理学会研究報告(Web) 2023 ( AL-192 ) 2023
-
Algorithms for Optimally Shifting Intervals under Intersection Graph Models
HONORATO DROGUETT Nicolas, KURITA Kazuhiro, HANAKA Tesshu, ONO Hirotaka
電子情報通信学会技術研究報告(Web) 123 ( 325(COMP2023 16-27) ) 2023
-
要素数制約付き極大マトロイド共通独立集合の多項式遅延列挙
小林靖明, 栗田和宏, 和佐州洋
日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2023 2023
-
Analysis of 20th French Philosophers Network using Wikipedia Data
2022 193 - 198 2022.12
-
Efficient Enumeration of Spanning Subgraphs in Planar Graphs with Edge Connectivity Constraints
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
2022.10
-
平面グラフ中の極小全域2辺連結部分グラフの多項式遅延列挙
小林靖明, 栗田和宏, 和佐州洋
情報処理学会 第84回全国大会 革新的アルゴリズム基盤の構築に向けて 2022.3
-
Collecting Balls on a Line by Robots with Limited Energy
Nicolas Honorato Drogue, Kazuhiro Kurita, Tesshu Hanaka, Yota Otachi, Hirotaka Ono
IEICE Trans. Inf. Syst. 107 ( 3 ) 325 - 327 2022.2
-
Approximation Algorithms for Finding Max-Sum Diverse Collections
JSAI Technical Report, SIG-FPAI 119 21 - 26 2022
-
Designing Space-Efficient Top-k Enumeration Algorithms
KOBAYASHI Yasuaki, KURITA Kazuhiro
人工知能学会人工知能基本問題研究会資料 117th 2021
-
Algorithms for Finding Diverse Subgraphs
HAKANA Tesshu, KOBAYASHI Yasuaki, KURITA Kazuhiro, OTACHI Yota
人工知能学会人工知能基本問題研究会資料 113th 2020
-
Subgraph Enumeration: Efficient Algorithms and Empirical Studies International journal
Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
The 2nd International Workshop on Enumeration Problems & Application 2018.11
-
Kurita Kazuhiro, Wasa Kunihiro, Arimura Hiroki, Uno Takeaki
( 2088 ) 44 - 52 2018.8
-
栗田 和宏, Alessio Conte, 和佐 州洋, 宇野 毅明, 有村 博紀
第80回全国大会講演論文集 2018 ( 1 ) 347 - 348 2018.3
-
Graph Classification Based on Graph Pattern Tries
105 63 - 68 2018.1
-
Enumeration and Random Sampling of Nonisomorphic Two-Terminal Series-Parallel Graphs
伝住周平, 堀山貴史, 栗田和宏, 中畑裕, 鈴木浩史, 和佐州洋, 山崎一明
電子情報通信学会技術研究報告 118 ( 216(COMP2018 9-20)(Web) ) 2018
-
Efficient Enumeration of Dominating Sets in k-degenerate Graphs (情報セキュリティ)
栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 117 ( 369 ) 111 - 117 2017.12
-
Efficient Enumeration of Dominating Sets in k-degenerate Graphs (コンピュテーション)
栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 117 ( 370 ) 111 - 117 2017.12
-
グラフに含まれる誘導マッチングの列挙
栗田和宏, 和佐州洋, 喜田拓也, 有村博紀
情報処理学会研究報告(Web) 2016 ( AL-157 ) 2016
-
D-032 Faster pattern matching algorithm for 2-dimentional trajectory data
Yamamoto Masahiro, Kurita Kazuhiro, Sasakawa Hirohito, Arimura Hiroki
13 ( 2 ) 153 - 154 2014.8
Awards
-
研究会優秀賞
2020.6 人工知能学会 多様な部分グラフを発見するアルゴリズム
土中 哲秀, 小林 靖明, 栗田 和宏, 大舘 陽太
Research Projects
-
文字列に対するアルファベット順序最適化理論
Grant number：25K00136 2025.04 - 2030.03
日本学術振興会 科学研究費助成事業 基盤研究(B)
中島 祐人, 坂内 英夫, 栗田 和宏
Grant amount：\18720000 （ Direct expense: \14400000 、 Indirect expense：\4320000 ）
-
Design a theoretical foundation of the hardness of enumeration problems
Grant number：25K03080 2025.04 - 2030.03
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
和佐 州洋, 山中 克久, 栗田 和宏
Grant amount：\18720000 （ Direct expense: \14400000 、 Indirect expense：\4320000 ）
-
部分グラフ列挙問題に対する計算困難性の精緻化
Grant number：25K21273 2025.04 - 2030.03
日本学術振興会 科学研究費助成事業 若手研究
栗田 和宏
Grant amount：\4810000 （ Direct expense: \3700000 、 Indirect expense：\1110000 ）
-
文学的読解を通じた意図の推察に基づくSNS上の誹謗中傷・悪口の分析手法の開発
Grant number：24K15204 2024.04 - 2029.03
日本学術振興会 科学研究費助成事業 基盤研究(C)
武富有香, 杉山佳奈美, 須田永遠, 松田智裕, 栗田和宏
Grant amount：\4550000 （ Direct expense: \3500000 、 Indirect expense：\1050000 ）
-
Foundation of Japanese stylistics for social media analysis
Grant number：22K12285 2022.04 - 2027.03
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C) Grant-in-Aid for Scientific Research (C)
須田 永遠, 栗田 和宏, 武富 有香
Grant amount：\4290000 （ Direct expense: \3300000 、 Indirect expense：\990000 ）
本年度は、ソーシャルメディアの書き手の反応や心的状態の類型および言語的特徴に関する知見を獲得するため、実際に国内で影響力のある二つのソーシャルメディアを対象としてテキストデータを収集し、分析を行った。並行して本研究に必要なマイニング技術を下支えするアルゴリズムの開発も行い、これらの成果を国内外の会議や論文誌で発表した。詳細は以下の通りである。
(i) ワクチンに関する大規模なTwitterデータの分析：新型コロナウイルスワクチン接種期間中にTwitterで投稿された「ワクチン」の語を含む１億件以上の日本語の全ツイートデータを収集し、クラスタリング技術を用いてトピックごとに分類し、人手による意味解釈とアノテーションを施した上で時系列解析を行った。その結果、職域接種の開始を境に、人々の関心が社会的トピックから個人的事柄へと推移したことが明らかになった。
(ii) Yahoo!コメント上の#metooに対する中傷の類型化とアノテーション：#metoo運動以降、Yahoo!コメントに現れるようになった女性に対する誹謗中傷的ナラティヴを人手で読解・精査し、類型を作成、その類型にしたがってコメントにアノテーションを行うことで性暴力トピックに対する書き手の典型的な反応を析出し、反応の分布を明らかにした。その結果の一部は従来のミソジニーに関する人文学的研究の知見を定量的に証明するものとなった。
(iii) テキストマイニング技術の基礎となるアルゴリズムの開発：大量のテキストデータから書き手の心的状態と結びついた言語的特徴の累計を析出するには、まず限られたテキストを人手で解釈する必要があるが、その際にはある条件を満たす文を効率よくマイニングする情報学的な技術が必須である。こうした技術を下支えするアルゴリズム、本年度は特に条件をできるだけ満たす解（準最適解）を列挙するアルゴリズムの開発を行った。 -
列挙や数え上げなどを統一的に扱うための基盤技術
Grant number：22H03549 2022.04 - 2026.03
日本学術振興会 科学研究費助成事業 基盤研究(B) 基盤研究(B)
堀山 貴史, 伝住 周平, 和佐 州洋, 栗田 和宏, 脊戸 和寿, 中畑 裕
Grant amount：\17160000 （ Direct expense: \13200000 、 Indirect expense：\3960000 ）
列挙、数え上げ、サンプリングなどのアルゴリズムは、互いに深く関連しつつも、それぞれ独自の技法が必要とされることが多い。ここで、同じ制約条件のもとで、つまり同じ解空間において、解の列挙、数え上げなどタイプの異なるアルゴリズムそれぞれを個別に設計する状況を見つめ直し、アルゴリズム設計者が頭の中に持つ解空間に関する理解をもとにアルゴリズムを導出する過程を明らかにすることで、列挙、数え上げ、サンプリングなどのアルゴリズム設計を統一的に扱うための指針を与えることを本研究課題の目的としている。
本研究課題の研究者のみならず、課題外の連携研究者との議論も通して、列挙や数え上げなどのアルゴリズム設計の過程の再検討を行った。具体的には、たとえば、グラフの同型性の観点から代表元のみを列挙する同型性の除去について、ZDD (Zero-Suppressed Binary Decision Disgrams; 零抑制型二分決定グラフ) を用いるアプローチの検討を行った。制約条件を満たす解集合をうまく区分し、それらの区分された解集合相互の関係を表す方法を検討する際に、非同型なものを漏れなく重複なく求められる保証を与える必要があり、具体的なアルゴリズム設計を通して、アルゴリズム設計とアイデア記述に関する知見を得た。また、列挙と深い関連を持つ組合せ遷移問題も含めて、関連分野への応用に関する検討を行った。具体的には、たとえば、45度系格子パターン上での折り紙の展開図の列挙と数え上げの技法についてである。この問題では、縦横および斜め45度方向の格子上のみに折り線の位置を限定し、各頂点で平坦に折ることのできる局所平坦性を制約として、展開図の列挙または数え上げを行っている。また、格子の規則性から、回転および鏡映反転による同型性を考慮する必要があり、応用上の要請だけでなく、本研究課題の方向性にも沿った研究成果である。 -
部分グラフ列挙問題で用いる多項式遅延列挙アルゴリズム設計技法の拡張に関する研究
Grant number：21H05861 2021.09 - 2023.03
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Transformative Research Areas (A) Grant-in-Aid for Transformative Research Areas (A)
栗田 和宏
Authorship：Principal investigator
Grant amount：\2600000 （ Direct expense: \2000000 、 Indirect expense：\600000 ）
本年度は独立性システムに関する列挙問題とマトロイドに関する列挙問題の特殊系となるグラフの列挙問題について研究を行った．
独立性システムの列挙に関しては k -拡張システムの極大解列挙アルゴリズムの構築に取り組んだ．これは定義から， k が定数であるならば多項式遅延で列挙できることがわかった．しかし，この結果の興味深い点は，多項式遅延列挙ができるが入力制約問題が多項式時間で解けるかがわかっていないという点である．そこで，次なる課題として，入力制約問題が多項式時間で解けるかを調べるために具体的な離散構造の列挙問題に取り組んだ．その問題として，マトロイドマッチングについて研究を行った．マトロイドマッチングは組合せ最適化分野で古くから知られる離散構造であり，二部グラフマッチングの一般化となっている．この問題は最適化問題としてはNP-困難であることが知られているが，列挙問題としてみた時，マトロイドマッチングの特殊系の問題は入力制約問題が多項式時間で解けることに気づいた．そこで，マトロイドマッチングについての列挙問題を研究したところ，マトロイドマッチングが2-拡張可能システムであることがわかった．この結果はグラフをハイパーグラフに拡張した場合，ハイパー辺のサイズが定数 k であればマトロイドマッチングは k-拡張可能システムになることがわかった．従って，この構造は多項式遅延で列挙できることがわかったが，まだ入力制約問題が多項式時間で解ける反例は得られなかった．
次に，マトロイドに関連するグラフ上の列挙問題としてはグラフ中の極小な全域2辺連結部分グラフを列挙する問題について研究を行い，グラフが平面的である場合はこの問題は多項式遅延が可能であると予想する．これは平面グラフにおいて，辺連携性と最小サイクルが非常に深い関係があるため，その知見を用いた良いアルゴリズムが設計できるためである． -
A Method for Analyzing Collective Behavior Based on Structuring Topics on Large-Scale SNS
Grant number：21H03559 2021.04 - 2026.03
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B) Grant-in-Aid for Scientific Research (B)
橋本 隆子, 宇野 毅明, 栗田 和宏, 申 吉浩, 小林 亮太, 久保山 哲二
Grant amount：\16900000 （ Direct expense: \13000000 、 Indirect expense：\3900000 ）
1. Two-Stage Clustering 手法の開発
2021年度は、SNSにおける人々の反応を分析するために、マイクロクラスタリングと時系列クラスタリングを組み合わせた Two-Stage Clustering 手法を提案し、コロナワクチンに対するTwitterデータ（全量データ）の分析を行った。この手法は、これまで内容の類似度に加えて、時系列上のパターン類似度を考慮できる効率的な手法であり、これにより、コロナワクチンに関する12M以上のTweet集合を、速報ニュースへの反応、Tweetへの反応、その他（デマなど）に分類できることを示した。結果を論文としてまとめ、BigData2021にも採択された。また招待講演等でも紹介を行った。
２. コロナワクチンに関する人々の反応評価（時系列分析）
さらにTwitterの全量データを対象として、コロナワクチンに対する人々の反応のセンチメント分析（時系列評価）にも取り組んでおり、コロナワクチンに対する日本国民の気持ちが時間とともにどのような変遷をたどったかについて考察している。結果は、近日中に社会科学系のジャーナルに投稿予定である。
3. マイクロクラスタリング手法の改良
大規模データに対応可能とするために、マイクロクラスタリング手法を、より類似度の高いインスタンスを初期のタイミングで集約する改良を行った。これにより、数千万件規模のTwitterデータが標準的なPC上でリーズナブルな速度で分析可能となった。大規模データ分析において、極めて重要な成果であると認識している。 -
サイズ制約付き極小部分集合列挙問題に対する多項式遅延近似列挙アルゴリズムの研究
Grant number：21K17812 2021.04 - 2025.03
日本学術振興会 科学研究費助成事業 若手研究 若手研究
栗田 和宏
Grant amount：\4810000 （ Direct expense: \3700000 、 Indirect expense：\1110000 ）
今年度は列挙アルゴリズムに関する3編の論文を執筆し，うち1編がデータベース分野のトップ会議であるPODS 2022に採択された．また，列挙アルゴリズムの新たな応用として，ある離散構造の重み和が重い順に上位k個を効率良く計算するアルゴリズムが存在すれば，そのアルゴリズムを用いて多様な組合せ構造を発見する効率良い近似アルゴリズムを開発した．この結果も論文化して現在国際会議に投稿中である．
列挙アルゴリズム，特に最適化制約を加えた列挙問題に対する近似的な列挙アルゴリズムについては，入力制約問題という特殊な列挙問題が解ける問題に関して，効率良い近似列挙アルゴリズムを与えた．この結果は現在アルゴリズム分野の学術雑誌であるdiscrete applied mathematicsに投稿中である．さらに，この論文で開発した技法を適用できる新たな問題も発見した．具体的には極小な連結辺支配集合が近似的に列挙できることを明らかにした．列挙において頂点に関する連結性を扱うことはしばしば困難になるため，本研究では辺に関する連結性を持つ問題に関して列挙アルゴリズムが構成できるかどうかを研究した．この結果は現在プレプリントとして公開している．
また，近似的な列挙アルゴリズムは列挙の困難性と最適化の困難性を同時に持つため，近似的な列挙アルゴリズムの研究のためには最適化制約を除いた場合の列挙の研究を深めることも重要である．そこで，本年度は極小なシュタイナー木という辺の連結性に関するグラフの構造に対し，効率良い列挙アルゴリズムの研究を行った．この構造の列挙は2000年台中盤にデータベース分野でも行われており，グラフアルゴリズム分野以外でも興味が持たれている問題である．今年度はこの問題に対して線型遅延の効率良い列挙アルゴリズムを与え，PODS 2022に採択された． -
2021 - 2023
科学技術振興機構 戦略的な研究開発の推進 戦略的創造研究推進事業 ACT-X
栗田 和宏
Authorship：Principal investigator
本研究では列挙アルゴリズムの理論と実用のギャップの要因である出力数による計算コストの増加の解決を目指します。列挙では少なくとも出力数に依存した時間が必要です。出力数は膨大なため、効率良い列挙でも膨大な計算コストが必要です。そこで、本研究では出力数を調整可能にするため、順序制約つき列挙に着目します。これにより出力の網羅性と計算コストのトレードオフを実現し、利便性の高い列挙のための基盤技術開発を行います。
-
疎なグラフに対する効率良い部分構造列挙アルゴリズムの研究
Grant number：19J10761 2019.04 - 2021.03
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for JSPS Fellows Grant-in-Aid for JSPS Fellows
栗田 和宏
Grant amount：\1700000 （ Direct expense: \1700000 ）
本年度は極大性，極小性を満たす部分グラフ列挙アルゴリズムの開発に加え，サイズ-k列挙アルゴリズムの構築を行なった．その成果として，以下の結果が得られた.
（1) サイズ-k列挙アルゴリズムは，理論的に扱うことは困難であると考え，ヒューリスティックアルゴリズムの開発を予定していた．しかし，これまでの研究から，サイズ制約付きの列挙問題に対し，妥当な問題の定式化とそれに対する効率良い列挙アルゴリズムの開発に成功した．サイズ制約付き列挙問題を理論的に扱うことが困難な理由として，最適化問題の困難性がある．列挙問題が全ての解を見つける問題であることから，明らかに最適化問題より列挙問題の方が困難であるため，最適化問題の困難性から，サイズ制約付き列挙問題が困難である．この困難性を避けるため，本研究では最適化アルゴリズムのように，列挙問題に近似という概念を導入し，サイズ制約付き列挙問題に対し，近似制約付きの列挙問題を定義した．さらに本研究では近似的なサイズ制約付きの極小部分集合列挙問題に対し，元の列挙問題が容易であるならば，解1つあたり多項式時間で動作する近似列挙アルゴリズムを提案した．
（2）極小シュタイナー木や内周制約付き極大部分グラフといった疎な部分グラフを列挙する効率良い列挙アルゴリズムの開発を行った．前年度は疎なグラフから部分グラフを効率良くに発見するアルゴリズムを与えたが，本年度はグラフ中から疎な部分グラフを列挙するアルゴリズムについて研究を行い，疎なグラフの中でも代表的な疎なグラフである木構造と，局所的に木構造を持つ内周制約付き極大部分グラフ列挙について研究を行なった．これらの問題に対し，極小シュタイナー木については解1つあたり線形時間，極大内周制約付き部分グラフ列挙については1つあたり多項式時間といった効率良い列挙アルゴリズムが得られた．
Class subject in charge
-
Safety and Security Managements for Engineer （2025academic year） Third semester - 金5～6
-
Safety and Security Managements for Engineer （2025academic year） Third semester - 金5～6
-
Information Technology Experiments B (Media Processing) （2025academic year） Third semester - 火3～7,金3～7
-
Information Technology Experiments C (Computer Software) （2025academic year） Fourth semester - 火3～7,金3～7
-
Mathematical Logic （2025academic year） Third semester - 水3～4
-
Mathematical Logic （2025academic year） Third semester - 水3～4