研究者詳細

顔写真

タムラ　ユウマ
田村　祐馬
Yuma Tamura
所属
大学院情報科学研究科　システム情報科学専攻　知能情報科学講座（アルゴリズム論分野）
職名
助教
学位

  • 博士（情報科学）（東北大学）

  • 修士（情報科学）（東北大学）

e-Rad 研究者番号
30907457

経歴 2

  • 2021年4月 ～ 継続中
    東北大学 大学院情報科学研究科　助教

  • 2020年4月 ～ 2021年3月
    独立行政法人日本学術振興会　特別研究員（DC2）

研究キーワード 3

  • 組合せ遷移

  • パラメータ化計算量

  • グラフアルゴリズム

研究分野 1

  • 情報通信 / 情報学基礎論 /

受賞 4

  1. The 19th International Conference and Workshop on Algorithms and Computation (WALCOM2025) The Best Paper Award

    2025年2月

  2. 第17回 野口研究奨励賞

    2022年6月　情報処理学会 東北支部

  3. 2021年度コンピュータサイエンス領域奨励賞

    2021年6月　一般社団法人 情報処理学会

  4. The 14th International Conference and Workshop on Algorithms and Computation (WALCOM2020) The Best Student Paper Award

    2020年4月

論文 17

  1. Changing induced subgraph isomorphisms under extended reconfiguration rules 国際誌 査読有り

    Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 19th International Conference and Workshops on Algorithms and Computation (WALCOM 2025)　15411　346-360　2025年2月

    DOI： 10.1007/978-981-96-2845-2_22 　

  2. Card-based zero-knowledge proof protocols for the 15-Puzzle and the token swapping problem 国際誌 査読有り

    Yuma Tamura, Akira Suzuki, Takaaki Mizuki

    Proceedings of the 11th ACM ASIA Public-Key Cryptography Workshop (APKC 2024)　11-22　2024年7月

    出版者・発行元： ACM

    DOI： 10.1145/3659467.3659905 　

  3. Parameterized complexity of weighted target set selection 国際誌 査読有り

    Takahiro Suzuki, Kei Kimura, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of Theory and Applications of Models of Computation - 18th Annual Conference (TAMC 2024)　14637　320-331　2024年5月

    DOI： 10.1007/978-981-97-2340-9_27 　

  4. Finding induced subgraphs from graphs with small mim-width 国際誌 査読有り

    Yota Otachi, Akira Suzuki, Yuma Tamura

    Proceedings of the 19th Scandinavian Symposium on Algorithm Theory (SWAT 2024)　294　38:1-38:16　2024年5月

    DOI： 10.4230/LIPIcs.SWAT.2024.38 　

  5. The shortest path reconfiguration problem based on relaxation of reconfiguration rules 国際誌 査読有り

    Naoki Domon, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 18th International Conference and Workshops on Algorithms and Computation (WALCOM 2024)　14549　227-241　2024年2月

    DOI： 10.1007/978-981-97-0566-5_17 　

  6. On the complexity of list $\mathcal H$-packing for sparse graph classes 国際誌 査読有り

    Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 18th International Conference and Workshops on Algorithms and Computation (WALCOM 2024)　14549　421-435　2024年2月

    DOI： 10.1007/978-981-97-0566-5_30 　

  7. On the routing problems in graphs with ordered forbidden transitions 国際誌 査読有り

    Kota Kumakura, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 29th International Computing and Combinatorics Conference (COCOON2023)　14422　359-370　2023年12月

    DOI： 10.1007/978-3-031-49190-0_26 　

    ISSN：0302-9743

    eISSN：1611-3349

  8. Happy set problem on subclasses of co-comparability graphs 国際誌 招待有り 査読有り

    Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura

    Algorithmica　85　(11)　3327-3347　2023年11月

    DOI： 10.1007/s00453-022-01081-0 　

    ISSN：0178-4617

    eISSN：1432-0541

  9. Decremental optimization of vertex-coloring under the reconfiguration framework 招待有り 査読有り

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    International Journal of Computer Mathematics: Computer Systems Theory　8　(1)　80-92　2023年4月

    DOI： 10.1080/23799927.2023.2185543 　

  10. Parameterized complexity of optimizing list vertex-coloring through reconfiguration 査読有り

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 17th International Conference and Workshops on Algorithms and Computation (WALCOM2023)　13973　279-290　2023年3月

    DOI： 10.1007/978-3-031-27051-2_24 　

  11. Happy set problem on subclasses of co-comparability graphs 査読有り

    Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura

    Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM2022)　13174　149-160　2022年3月

    出版者・発行元： Springer

    DOI： 10.1007/978-3-030-96731-4_13 　

  12. Decremental optimization of vertex-coloring under the reconfiguration framework 査読有り

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 27th International Conference on Computing and Combinatorics (COCOON 2021)　13025　355-366　2021年10月

    出版者・発行元： Springer

    DOI： 10.1007/978-3-030-89543-3_30 　

  13. Approximability of the independent feedback vertex set problem for bipartite graphs 招待有り 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Theoretical Computer Science　849　227-236　2021年1月

    DOI： 10.1016/j.tcs.2020.10.026 　

  14. Minimization and parameterized variants of vertex partition problems on graphs 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC2020)　181　40:01-40:13　2020年12月

    出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.ISAAC.2020.40 　

  15. Approximability of the independent feedback vertex set problem for bipartite graphs 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Proceedings of the 14th International Conference and Workshop on Algorithms and Computation (WALCOM2020)　12049　286-295　2020年3月

    出版者・発行元： Springer

    DOI： 10.1007/978-3-030-39881-1_24 　

  16. Algorithms for the independent feedback vertex set problem 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences　E98-A　(6)　1179-1188　2015年6月

    DOI： 10.1587/transfun.E98.A.1179 　

  17. Deterministic algorithms for the independent feedback vertex set problem 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Proceedings of the 25th International Workshop on Combinatorial Algorithms (IWOCA 2014)　8986　351-363　2014年10月

    出版者・発行元： Springer

    DOI： 10.1007/978-3-319-19315-1_31 　

︎全件表示 ︎最初の5件までを表示

MISC 13

  1. Independent Set and Vertex Cover Reconfiguration Under Extended Rules

    情報処理学会 第203回アルゴリズム研究会　2025-AL-203　(4)　1-6　2025年5月

  2. グラフ構造を用いたメンバーシップ支配集合問題の計算複雑性に関する研究

    若山 大智, 鈴木 顕, 田村 祐馬, 周 暁

    情報処理学会 第203回アルゴリズム研究会　2025-AL-203　(11)　1-8　2025年5月

  3. List variants of packing problems on sparse graphs

    情報処理学会 第196回アルゴリズム研究会　2024-AL-196　(5)　1-7　2024年1月

  4. Shortest path reconfiguration with relaxed constraints

    情報処理学会 第196回アルゴリズム研究会　2024-AL-196　(6)　1-7　2024年1月

  5. 点重み付きグラフにおける標的集合選択問題に関する研究

    鈴木 隆央, 鈴木 顕, 田村 祐馬, 周 暁

    情報処理学会 第196回アルゴリズム研究会　2024-AL-196　(8)　1-6　2024年1月

  6. On the problems of finding paths to avoid ordered forbidden transitions based on graph structure

    情報処理学会 第195回アルゴリズム研究会　2023-AL-195　(24)　1-5　2023年11月

  7. Algorithms for happy set problem on interval graphs and permutation graphs

    情報処理学会 第186回アルゴリズム研究会　2022-AL-186　(7)　1-5　2022年1月

  8. Optimization variant of vertex-coloring reconfiguration problem

    情報処理学会 第185回アルゴリズム研究会　2021-AL-185　(13)　1-5　2021年11月

  9. Minimizing a vertex set satisfying specific graph properties

    情報処理学会 第180回アルゴリズム研究会　2020-AL-180　(4)　1-7　2020年11月

  10. Approximation of the independent feedback vertex set problem

    情報処理学会 第177回アルゴリズム研究会　2020-AL-177　(10)　1-5　2020年3月

  11. フィードバック独立点集合問題の計算複雑性

    田村 祐馬, 伊藤 健洋, 周 暁

    情報処理学会 第78回全国大会講演論文集　2016　(1)　399-400　2016年3月

  12. The independent feedback vertex set problem

    Proceedings of the 17th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2014)　11-18　2014年7月

  13. The independent feedback vertex set problem

    電子情報通信学会技術研究報告　114　(80)　13-18　2014年6月

︎全件表示 ︎最初の5件までを表示

講演・口頭発表等 7

  1. 完全スプリットグラフにおける支配集合グレイコード問題

    小海 虎丿介, 土門 直樹, 鈴木 顕, 鈴木 隆央, 田村 祐馬, 周 暁

    冬のLAシンポジウム2024　2025年1月28日

  2. Induced Subgraph Isomorphism Reconfiguration Under Extended Reconfiguration Rules

    菅 達皓, 鈴木 顕, 田村 祐馬, 周 暁

    冬のLAシンポジウム2024　2025年1月27日

  3. Independent set reconfiguration under extended reconfiguration rules

    Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Combinatorial Reconfiguration Workshop 2024　2024年10月9日

  4. Feedback vertex set discovery via reconfiguration

    斉藤 凜, 菅 達皓, 鈴木 隆央, 田村 祐馬

    夏のLAシンポジウム2024　2024年7月16日

  5. Algorithms for weighted target set selection

    2024年電子情報通信学会総合大会 COMP-AFSA学生シンポジウム　2024年3月6日

  6. 遷移ルールの緩和に基づく独立集合遷移問題

    菅 達皓, 鈴木 顕, 田村 祐馬, 周 暁

    2024年電子情報通信学会総合大会 COMP-AFSA学生シンポジウム　2024年3月5日

  7. フィードバック独立点集合問題の近似困難性

    田村 祐馬, 伊藤 健洋, 周 暁

    京都大学 数理解析研究所 共同研究 （公開型）「数理計画問題に対する理論とアルゴリズムの研究」　2019年8月5日

︎全件表示 ︎最初の5件までを表示

共同研究・競争的資金等の研究課題 2

  1. グラフの構造的パラメータに基づく汎用的アルゴリズムの構築

    田村 祐馬

    2021年8月30日 ～ 2023年3月31日

    詳細を見る 詳細を閉じる

    本研究では，一般的に解くことが困難であるグラフ上の組合せ最適化問題に対し，「mim-width」や「sim-width」といった，グラフの構造的パラメータを利用した効率的なアルゴリズムの構築を目標としている．本年度はそのような組合せ最適化問題の中でも「最大幸福頂点集合問題」を扱った．グラフGの頂点部分集合Sに対し，頂点v自身とその隣接点全てがSに含まれるとき，vは幸福であると呼ぶ．最大幸福頂点集合問題はグラフGと整数kが与えられたとき，サイズkの頂点部分集合Sのうち幸福な頂点数を最大化するものを見つける問題である． 本問題の既存研究では，グラフの構造的パラメータや特徴に基づいたアルゴリズムの構築が行われてきた．既存結果の1つに，区間グラフ上の多項式時間アルゴリズムが存在する．区間グラフはグラフアルゴリズム分野において，実用的・理論的，両方の観点から重要な立ち位置にあるグラフである．しかし，区間グラフに対する既存のアルゴリズムは計算時間が大きく，実用的とは言い難かった． そこで本研究では，区間グラフのmim-widthが小さいという性質を利用して，区間グラフのアルゴリズムを再構築し，計算時間を改善した．また，同様にmim-widthが小さいグラフとして置換グラフを挙げ，多項式時間アルゴリズムを新たに構築した．本研究で構築したアルゴリズムは，整数kの値が小さければ実用的にも高速に動作する． mim-widthが小さいグラフに対しては，様々な問題に多項式時間アルゴリズムを与えるフレームワークが既存研究で提案されている．しかし，今回扱った最大幸福頂点集合問題は，既存のフレームワークに直接的には合致しないものである．したがって，本研究でmim-widthが小さい区間グラフや置換グラフに対して多項式時間アルゴリズムを与えたことは，mim-widthの可能性を広げるものとして重要性を持つ．

  2. 擬似独立性を持つフィードバック点集合問題の提唱とアルゴリズムの開発

    田村 祐馬

    2020年4月24日 ～ 2022年3月31日

    詳細を見る 詳細を閉じる

    当該年度は初めに，擬似独立性を持つフィードバック点集合問題の中で最も基礎的な「フィードバック独立点集合問題」の研究に取り組んだ．その結果，本問題の入力が平面二部グラフであったとしても，近似解の導出は非常に難しいことを証明した．その一方で，最大次数が小さい二部グラフに対して高速な近似アルゴリズムを与えた．これら成果を論文としてまとめ，国際会議「The 14th International Conference and Workshop on Algorithms and Computation (WALCOM2020)」にて発表した結果，Best Student Paper Awardを受賞した．また，証明を補完した学術誌版は「Theoretical Computer Science」にて掲載された． 続いて，前述の結果の拡張を目的として「分割最小化問題」を提唱し，問題の計算複雑性の解析に取り組んだ．この「分割最小化問題」は，上記で述べた「フィードバック独立点集合問題」のみならず，研究課題に挙げた「擬似独立性を持つフィードバック点集合問題」，さらに理論計算機科学分野における様々な古典的問題の一般化となっている．本問題に対して，近似解の導出が困難となる十分条件を与えた．その一方で，FPTアルゴリズムという，最適解のサイズが小さいとき高速に動作するアルゴリズムを与えた．問題が特定の条件を満たしていれば困難性やアルゴリズムの結果が導けるという意味で，これらは多様な問題に対する計算複雑性を一度に与えた汎用的な結果となっている．これら成果を論文としてまとめ，国際会議「The 31st International Symposium on Algorithms and Computation (ISAAC2020)」にて発表した．また，学術誌には論文構成を推敲した後，投稿する予定でいる．