Details of the Researcher

PHOTO

Yuma Tamura
Section
Graduate School of Information Sciences
Job title
Assistant Professor
Degree

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

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

e-Rad No.
30907457

Research History 2

  • 2021/04 - Present
    Tohoku University

  • 2020/04 - 2021/03
    Japan Society for the Promotion of Science

Research Interests 3

  • Combinatorial Reconfiguration

  • Parameterized Complexity

  • グラフアルゴリズム

Research Areas 1

  • Informatics / Information theory /

Awards 4

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

    2025/02

  2. Noguchi Incentive Award

    2022/06　Tohoku branch of Information Processing Society of Japan

  3. IPSJ Computer Science Research Award for Young Scientists

    2021/06　Information Processing Society of Japan

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

    2020/04

Papers 17

  1. Changing induced subgraph isomorphisms under extended reconfiguration rules International-journal Peer-reviewed

    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/02

    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 International-journal Peer-reviewed

    Yuma Tamura, Akira Suzuki, Takaaki Mizuki

    Proceedings of the 11th ACM ASIA Public-Key Cryptography Workshop (APKC 2024)　11-22　2024/07

    Publisher: ACM

    DOI： 10.1145/3659467.3659905 　

  3. Parameterized complexity of weighted target set selection International-journal Peer-reviewed

    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/05

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

  4. Finding induced subgraphs from graphs with small mim-width International-journal Peer-reviewed

    Yota Otachi, Akira Suzuki, Yuma Tamura

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

    DOI： 10.4230/LIPIcs.SWAT.2024.38 　

  5. The shortest path reconfiguration problem based on relaxation of reconfiguration rules International-journal Peer-reviewed

    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/02

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

  6. On the complexity of list $\mathcal H$-packing for sparse graph classes International-journal Peer-reviewed

    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/02

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

  7. On the routing problems in graphs with ordered forbidden transitions International-journal Peer-reviewed

    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 International-journal Invited Peer-reviewed

    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 Invited Peer-reviewed

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    International Journal of Computer Mathematics: Computer Systems Theory　8　(1)　80-92　2023/04

    DOI： 10.1080/23799927.2023.2185543 　

  10. Parameterized complexity of optimizing list vertex-coloring through reconfiguration Peer-reviewed

    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/03

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

  11. Happy set problem on subclasses of co-comparability graphs Peer-reviewed

    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/03

    Publisher: Springer

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

  12. Decremental optimization of vertex-coloring under the reconfiguration framework Peer-reviewed

    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

    Publisher: Springer

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

  13. Approximability of the independent feedback vertex set problem for bipartite graphs Invited Peer-reviewed

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Theoretical Computer Science　849　227-236　2021/01

    DOI： 10.1016/j.tcs.2020.10.026 　

  14. Minimization and parameterized variants of vertex partition problems on graphs Peer-reviewed

    Yuma Tamura, Takehiro Ito, Xiao Zhou

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

    Publisher: 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 Peer-reviewed

    Yuma Tamura, Takehiro Ito, Xiao Zhou

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

    Publisher: Springer

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

  16. Algorithms for the independent feedback vertex set problem Peer-reviewed

    Yuma Tamura, Takehiro Ito, Xiao Zhou

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

    DOI： 10.1587/transfun.E98.A.1179 　

  17. Deterministic algorithms for the independent feedback vertex set problem Peer-reviewed

    Yuma Tamura, Takehiro Ito, Xiao Zhou

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

    Publisher: Springer

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

Show all ︎Show first 5

Misc. 13

  1. Independent Set and Vertex Cover Reconfiguration Under Extended Rules

    Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

    2025-AL-203　(4)　1-6　2025/05

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

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

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

  3. List variants of packing problems on sparse graphs

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

    2024-AL-196　(5)　1-7　2024/01

  4. Shortest path reconfiguration with relaxed constraints

    Naoki Domon, Akira Suzuki, Yuma Tamura, Xiao Zhou

    2024-AL-196　(6)　1-7　2024/01

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

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

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

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

    Kota Kumakura, Akira Suzuki, Yuma Tamura, Xiao Zhou

    2023-AL-195　(24)　1-5　2023/11

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

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

    2022-AL-186　(7)　1-5　2022/01

  8. Optimization variant of vertex-coloring reconfiguration problem

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    2021-AL-185　(13)　1-5　2021/11

  9. Minimizing a vertex set satisfying specific graph properties

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    2020-AL-180　(4)　1-7　2020/11

  10. Approximation of the independent feedback vertex set problem

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    2020-AL-177　(10)　1-5　2020/03

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

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

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

  12. The independent feedback vertex set problem

    Yuma Tamura, Takehiro Ito, Xiao Zhou

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

  13. The independent feedback vertex set problem

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    114　(80)　13-18　2014/06

Show all ︎Show first 5

Presentations 7

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

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

    冬のLAシンポジウム2024　2025/01/28

  2. Induced Subgraph Isomorphism Reconfiguration Under Extended Reconfiguration Rules

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

    冬のLAシンポジウム2024　2025/01/27

  3. Independent set reconfiguration under extended reconfiguration rules

    Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Combinatorial Reconfiguration Workshop 2024　2024/10/09

  4. Feedback vertex set discovery via reconfiguration

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

    夏のLAシンポジウム2024　2024/07/16

  5. Algorithms for weighted target set selection

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

    2024/03/06

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

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

    2024年電子情報通信学会総合大会 COMP-AFSA学生シンポジウム　2024/03/05

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

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

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

Show all Show first 5

Research Projects 2

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

    田村 祐馬

    Offer Organization: 日本学術振興会

    System: 科学研究費助成事業

    Category: 研究活動スタート支援

    Institution: 東北大学

    2021/08/30 - 2023/03/31

    More details Close

    本研究では，一般的に解くことが困難であるグラフ上の組合せ最適化問題に対し，「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. 擬似独立性を持つフィードバック点集合問題の提唱とアルゴリズムの開発

    田村 祐馬

    Offer Organization: 日本学術振興会

    System: 科学研究費助成事業

    Category: 特別研究員奨励費

    Institution: 東北大学

    2020/04/24 - 2022/03/31

    More details Close

    当該年度は初めに，擬似独立性を持つフィードバック点集合問題の中で最も基礎的な「フィードバック独立点集合問題」の研究に取り組んだ．その結果，本問題の入力が平面二部グラフであったとしても，近似解の導出は非常に難しいことを証明した．その一方で，最大次数が小さい二部グラフに対して高速な近似アルゴリズムを与えた．これら成果を論文としてまとめ，国際会議「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)」にて発表した．また，学術誌には論文構成を推敲した後，投稿する予定でいる．