Yutaro YAMAGUCHI

(Last Update: Sep 7, 2026)

Associate Professor
Department of Information and Physical Sciences,
Graduate School of Information Science and Technology,
Osaka University

Information Science and Technology Building C, Room C506,
1-5 Yamadaoka, Suita, Osaka 565-0871, Japan

Email: yutaro.yamaguchi [at] ist.osaka-u.ac.jp
(old: ymgc [at] kurims.kyoto-u.ac.jp, yutaro_yamaguchi [at] mist.i.u-tokyo.ac.jp, yutaro_yamaguchi [at] ist.osaka-u.ac.jp, yutaro_yamaguchi [at] inf.kyushu-u.ac.jp)    

>> Japanese Version

C.V.
Education

Mar. 2008: Graduation from Tennoji High School attached to Osaka Kyoiku University, Japan.

Mar. 2011: Withdrawal from Undergraduate School of Informatics and Mathematical Science,
     Faculty of Engineering, Kyoto University, Japan. (Due to proceeding to master's course.)

Mar. 2013: Master of Science from Department of Mathematical Sciences,
     Graduate School of Science, Kyoto University, Japan.

Mar. 2016: Doctor of Philosophy in the field of Mathematical Informatics from Department of Mathematical Informatics,
     Graduate School of Information Science and Technology, University of Tokyo, Japan.

Work

Feb. 2013 – Mar. 2013: Project Assistant of JST ERATO Kawarabayashi Large Graph Project (Link)
          "The Network Graph Theories and Optimization" Group.

Apr. 2013 – Mar. 2016: Research Fellow of the Japan Society for the Promotion of Science (DC1).

Apr. 2016 – Feb. 2020: Assistant Professor at Osaka University.

Aug. 2017 – Feb. 2020: Visiting Researcher at Discrete Optimization Unit, RIKEN Center for Advanced Intelligence Project.

Mar. 2020 – Aug. 2021: Associate Professor at Kyushu University.

Jun. 2020 – Oct. 2020: Visiting Researcher at Discrete Optimization Unit, RIKEN Center for Advanced Intelligence Project.

Sep. 2021 – Today: Associate Professor at Osaka University.

Joint Research

Apr. 2013 – Mar. 2018: Research Collaborator of JST ERATO Kawarabayashi Large Graph Project (Link)
          "The Network Graph Theories and Optimization" Group.

Aug. 2013 – Sep. 2013: Visit to NEC Laboratories at Kawasaki, Kanagawa, Japan.

Feb. 2014 – Mar. 2014: Visit to NEC Laboratories America at Cupertino, California, U.S.

Oct. 2014 – Mar. 2020: Research Collaborator of "Developing Optimal Modeling Methods for Large-Scale Complex Systems" Team (Link)
          in JST CREST "Modeling Methods allied with Modern Mathematics" Area.

Sep. 2019 – Nov. 2019: Visit to Egerváry Research Group on Combinatorial Optimization (EGRES) in Eötvös Loránd University, Hungary.

Feb. 2023 – May 2023: Visit to Egerváry Research Group on Combinatorial Optimization (EGRES) in Eötvös Loránd University, Hungary.

Teaching

Oct. 2013 – Mar. 2014: Teaching Assistant of the class "Algorithm Design" at Department of Mathematical Informatics,
          Graduate School of Information Science and Technology, University of Tokyo.

Oct. 2014 – Mar. 2015: Teaching Assistant of the class "Algorithm Design" at Department of Mathematical Informatics,
          Graduate School of Information Science and Technology, University of Tokyo.

Apr. 2015 – Aug. 2015: Teaching Assistant of "First-Year Seminar for Natural Sciences Students" (Theme: Introduction to Operations Research)
          at College of Arts and Sciences, University of Tokyo.

1st Semester in 2017: "Information Literacy A" at Division of Applied Science, School of Engineering, Osaka University.

2nd Semester in 2017: "Exercises in Information Physics and Sciences I" at Department of Applied Physics, School of Engineering, Osaka University.

1st Semester in 2018: "Information Literacy A" at Division of Applied Science, School of Engineering, Osaka University.

2nd Semester in 2018: "Exercises in Information Physics and Sciences I" at Department of Applied Physics, School of Engineering, Osaka University.

2nd Semester in 2019: "Exercises in Information Physics and Sciences I" at Department of Applied Physics, School of Engineering, Osaka University.

1st Semester in 2020: "Introduction to Computational Complexity"
          at Section of Informatics in Department of Physics, School of Science, Kyushu University.

2nd Semester in 2020: "Study on Information Science"
          at Section of Informatics in Department of Physics, School of Science, Kyushu University.

1st Semester in 2021: "Introduction to Computational Complexity"
          at Section of Informatics in Department of Physics, School of Science, Kyushu University.

2nd Semester in 2021: "Mathematical Programming" at Department of Applied Physics, School of Engineering, Osaka University.

2nd Semester in 2021: "Mathematical Analysis II" at School of Engineering, Osaka University.

1st Semester in 2022: "Mathematical Programming" at Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University.

1st Semester in 2022: "Advanced Operations Research" at Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University.

2nd Semester in 2022: "Mathematical Programming" at Department of Applied Physics, School of Engineering, Osaka University.

2nd Semester in 2022: "Mathematical Analysis II" at School of Engineering, Osaka University.

1st Semester in 2023: "Advanced Operations Research" at Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University.

2nd Semester in 2023: "Mathematical Programming" at Department of Applied Physics, School of Engineering, Osaka University.

1st Semester in 2024: "Mathematical Programming" at Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University.

1st Semester in 2024: "Advanced Operations Research" at Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University.

1st Semester in 2024: "A Door to Academia: Theory of Algorithms: Super-Introduction from Exits" at Center for Education in Liberal Arts and Sciences, Osaka University.

2nd Semester in 2024: "Mathematical Programming" at Department of Applied Physics, School of Engineering, Osaka University.

1st Semester in 2025: "Mathematical Programming" at Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University.

1st Semester in 2025: "Advanced Operations Research" at Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University.

1st Semester in 2025: "Mathematical Programming" at Department of Applied Physics, School of Engineering, Osaka University.

2nd Semester in 2025: "Fundamentals of Information Science" at Department of Applied Physics, School of Engineering, Osaka University.

1st Semester in 2026: "Mathematical Programming" at Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University.

1st Semester in 2026: "Advanced Operations Research" at Department of Information and Physical Sciences, Graduate School of Information Science and Technology, Osaka University.

1st Semester in 2026: "Mathematical Programming" at Department of Applied Physics, School of Engineering, Osaka University.

2nd Semester in 2026: "Fundamentals of Information Science" at Department of Applied Physics, School of Engineering, Osaka University.

Grants

Apr. 2013 – Mar. 2016: Grant-in-Aid for JSPS Research Fellow (No. 13J02522).

Aug. 2016 – Mar. 2018: JSPS KAKENHI, Grant-in-Aid for Research Activity Start-up (No. 16H06931).

Dec. 2016 – Mar. 2018: JST ACT-I "Information and Future" (No. JPMJPR16UR).

Apr. 2020 – Mar. 2024: JSPS KAKENHI, Grant-in-Aid for Early-Career Scientists (No. 20K19743).

Apr. 2020 – Mar. 2025: JSPS KAKENHI, Grant-in-Aid for Scientific Research (A) (No. 20H00605). [Co-Investigator]

Apr. 2025 – Mar. 2030: JSPS KAKENHI, Grant-in-Aid for Scientific Research (A) (No. 25H01114). [Co-Investigator]

Society (International)

During 2015: A student member of the Institute of Electrical and Electronics Engineers (IEEE) (No. 93303728).

During 2024: A regular member of Society for Industrial and Applied Mathematics (SIAM) (No. 020109561).

Committee (International)

Jan. 2020: Organizer of RIMS Project Research "International Workshop on Combinatorial Optimization and Algorithmic Game Theory".

Dec. 2021: Local Organizer of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021).

Dec. 2023: Local Organizer of the 34th International Symposium on Algorithms and Computation (ISAAC 2023).

Jan. 2026 – Today: Editorial Board of SIAM Journal on Discrete Mathematics (SIDMA).

Research Interests
Combinatorial Optimization, Graph Theory, Matroid Theory, Discrete Algorithms, Game Theory, Quantum Computing, etc.
Pubilications
Refereed Journal Articles
  1. Ryo Suzuki, Yutaro Yamaguchi:
    Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model.
    IEICE Transactions on Information and Systems, accepted.
  2. Kristóf Bérczi, Tamás Király, Yusuke Kobayashi, Yutaro Yamaguchi, Yu Yokoi:
    Finding Spanning Trees with Perfect Matchings.
    Discrete Applied Mathematics, 371 (2025), pp. 137–147. (DOI: 10.1016/j.dam.2025.04.001)
  3. Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama, Jun Kawahara, Ichigaku Takigawa, Yutaro Yamaguchi:
    Fast Enumeration of All Cost-Bounded Solutions for Combinatorial Problems Using ZDDs.
    Discrete Applied Mathematics, 360 (2025), pp. 467–486. (DOI: 10.1016/j.dam.2024.10.003)
  4. Hitoshi Murakami, Yutaro Yamaguchi:
    An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems.
    IEICE Transactions on Information and Systems, E108-D:3 (2025), pp. 214–220. (DOI: 10.1587/transinf.2024FCP0009)
  5. Alpár Jüttner, Csaba Király, Lydia Mirabel Mendoza-Cadena, Gyula Pap, Ildikó Schlotter, Yutaro Yamaguchi:
    Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions.
    Discrete Applied Mathematics, 357 (2024), pp. 34–50. (DOI: 10.1016/j.dam.2024.05.044)
  6. Kohei Morita, Shinya Shiroshita, Yutaro Yamaguchi, Yu Yokoi:
    Fast Primal-Dual Update against Local Weight Update in Linear Assignment Problem and Its Application.
    Information Processing Letters, 183 (2024), No. 106432, 7pp. (DOI: 10.1016/j.ipl.2023.106432)
  7. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Matroid Intersection under Restricted Oracles.
    SIAM Journal on Discrete Mathematics, 37:2 (2023), pp. 1311–1330. (DOI: 10.1137/22M152579X)
  8. Kristóf Bérczi, Tamás Király, Tamás Schwarcz, Yutaro Yamaguchi, Yu Yokoi:
    Hypergraph Characterization of Split Matroids.
    Journal of Combinatorial Theory, Series A, 194 (2023), No. 105697, 15pp. (DOI: 10.1016/j.jcta.2022.105697)
  9. Yoichi Iwata, Yutaro Yamaguchi:
    Finding a Shortest Non-zero Path in Group-Labeled Graphs.
    Combinatorica, 42 (2022), pp. 1253–1282. (DOI: 10.1007/s00493-021-4736-x)
  10. Takanori Maehara, So Nakashima, Yutaro Yamaguchi:
    Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice — Continuous Greedy Algorithm on Median Complex —.
    Mathematical Programming (Series A), 194 (2022), pp. 85–119. (DOI: 10.1007/s10107-021-01620-7)
  11. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems.
    Theoretical Computer Science, 910 (2022), pp. 48–53. (DOI: 10.1016/j.tcs.2022.01.035)
  12. Yasuaki Kobayashi, Shin-ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka:
    An O(n2)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Convex Polygon.
    IEICE Transactions on Information and Systems, E105-D:3 (2022), pp. 503–507. (DOI: 10.1587/transinf.2021FCP0013)
  13. Yuya Masumura, Taihei Oki, Yutaro Yamaguchi:
    Dynamic Programming Approach to the Generalized Minimum Manhattan Network Problem.
    Algorithmica, 83 (2021), pp. 3681–3714. (DOI: 10.1007/s00453-021-00868-x)
  14. Kristóf Bérczi, Tamás Schwarcz, Yutaro Yamaguchi:
    List Coloring of Two Matroids through Reduction to Partition Matroids.
    SIAM Journal on Discrete Mathematics, 35:3 (2021), pp. 2192–2209. (DOI: 10.1137/20M1385615)
  15. Yuval Filmus, Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi:
    Tight Approximation for Unconstrained XOS Maximization.
    Mathematics of Operations Research, 46:4 (2021), pp. 1599–1610. (DOI: 10.1287/moor.2020.1088)
  16. Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi:
    Finding a Path with Two Labels Forbidden in Group-Labeled Graphs.
    Journal of Combinatorial Theory, Series B, 143 (2020), pp. 65–122. (DOI: 10.1016/j.jctb.2019.12.001)
  17. Takanori Maehara, Yutaro Yamaguchi:
    Stochastic Packing Integer Programs with Few Queries.
    Mathematical Programming (Series A), 182 (2020), pp. 141–174. (DOI: 10.1007/s10107-019-01388-x)
  18. Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi:
    Subgame Perfect Equilibria of Sequential Matching Games.
    ACM Transactions on Economics and Computation, 7:4 (2020), No. 21, 30pp. (DOI: 10.1145/3373717)
  19. Yasushi Kawase, Yutaro Yamaguchi:
    Antimatroids Induced by Matchings.
    Discrete Applied Mathematics, 257 (2019), pp. 342–349. (DOI: 10.1016/j.dam.2018.09.032)
  20. Kristóf Bérczi, Satoru Iwata, Jun Kato, Yutaro Yamaguchi:
    Making Bipartite Graphs DM-irreducible.
    SIAM Journal on Discrete Mathematics, 32:1 (2018), pp. 560–590. (DOI: 10.1137/16M1106717)
  21. Shin-ichi Tanigawa, Yutaro Yamaguchi:
    Packing Non-zero A-paths via Matroid Matching.
    Discrete Applied Mathematics, 214 (2016), pp. 169–178. (DOI: 10.1016/j.dam.2016.06.001)
  22. Yutaro Yamaguchi:
    Realizing Symmetric Set Functions as Hypergraph Cut Capacity.
    Discrete Mathematics, 339:8 (2016), pp. 2007–2017. (DOI: 10.1016/j.disc.2016.02.010)
  23. Yutaro Yamaguchi:
    Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity.
    SIAM Journal on Discrete Mathematics, 30:1 (2016), pp. 474–492. (DOI: 10.1137/130949877)
  24. Yutaro Yamaguchi, Anna Ogawa, Akiko Takeda, Satoru Iwata:
    Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms.
    IEEE Transactions on Smart Grid, 6:5 (2015), pp. 2189–2199. (DOI: 10.1109/TSG.2015.2394791)
Refereed Conference Proceedings
  1. Daisuke Shibatani, Yutaro Yamaguchi:
    Envy-Free School Redistricting Between Two Groups.
    Proceedings of the 32nd International Computing and Combinatorics Conference (COCOON 2026), pp. 342–354. (DOI: 10.1007/978-981-92-3309-0_26)
  2. Takashi Horiyama, Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Akira Suzuki, Ryuhei Uehara, Yutaro Yamaguchi:
    Computational Complexity of Swish Is Solved.
    Proceedings of the 13th International Conference on Fun With Algorithms (FUN 2026), No. 25, 12pp. (DOI: 10.4230/LIPIcs.FUN.2026.25)
  3. Hiroki Shibata, Yuto Nakashima, Yutaro Yamaguchi, Shunsuke Inenaga:
    LZBE: An LZ-style Compressor Supporting O(log n)-Time Random Access.
    Proceedings of the 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026), No. 34, 18pp. (DOI: 10.4230/LIPIcs.CPM.2026.34)
    * Selected as Best Paper Award Honorable Mention.
  4. Yasuaki Kobayashi, Kazuhiro Kurita, Yutaro Yamaguchi:
    Finding One Local Optimum Is Easy — but What About Two?
    Proceedings of the 40th Annual AAAI Conference on Artificial Intelligence (AAAI 2026), pp. 37009–37017. (DOI: 10.1609/aaai.v40i43.41029)
  5. Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, Yutaro Yamaguchi:
    Towards the Proximity Conjecture on Group-Labeled Matroids.
    Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), No. 85, 17pp. (DOI: 10.4230/LIPIcs.ICALP.2025.85)
  6. Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi:
    A Nearly Linear-Time Distributed Algorithm for Exact Maximum Matching.
    Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pp. 4062–4082. (DOI: 10.1137/1.9781611977912.141)
  7. Yasuaki Kobayashi, Shin-ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka:
    Max-Min 3-dispersion on a Convex Polygon.
    Proceedings of the 37th European Workshop on Computational Geometry (EuroCG 2021), No. 9, 7pp.
  8. Yuya Masumura, Taihei Oki, Yutaro Yamaguchi:
    Dynamic Programming Approach to the Generalized Minimum Manhattan Network Problem.
    Proceedings of the 6th International Symposium on Combinatorial Optimization (ISCO 2020), pp. 237–248. (DOI: 10.1007/978-3-030-53262-8_20)
  9. Yutaro Yamaguchi: A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs.
    Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pp. 1923–1932. (DOI: 10.1137/1.9781611975994.118)
  10. Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida:
    0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms.
    Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018), pp. 462–473. (DOI: 10.1109/FOCS.2018.00051)
  11. Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi:
    Computing a Subgame Perfect Equilibrium of a Sequential Matching Game.
    Proceedings of the 19th ACM Conference on Economics and Computation (EC 2018), pp. 131–148. (DOI: 10.1145/3219166.3219200)
  12. Takanori Maehara, Yutaro Yamaguchi:
    Stochastic Packing Integer Programs with Few Queries.
    Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 293–310. (DOI: 10.1137/1.9781611975031.21)
  13. Yutaro Yamaguchi:
    Shortest Disjoint S-paths via Weighted Linear Matroid Parity.
    Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), No. 63, 13pp. (DOI: 10.4230/LIPIcs.ISAAC.2016.63)
  14. Naoto Ohsaka, Yutaro Yamaguchi, Naonori Kakimura, Ken-ichi Kawarabayashi:
    Maximizing Time-decaying Influence in Social Networks.
    Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD 2016), pp. 132–147. (DOI: 10.1007/978-3-319-46128-1_9)
  15. Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi:
    Finding a Path in Group-Labeled Graphs with Two Labels Forbidden.
    Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), pp. 797–809. (DOI: 10.1007/978-3-662-47672-7_65)
  16. Yutaro Yamaguchi, Anna Ogawa, Akiko Takeda, Satoru Iwata:
    Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms.
    Proceedings of the 5th IEEE International Conference on Smart Grid Communications (SmartGridComm 2014), pp. 830–835. (DOI: 10.1109/SmartGridComm.2014.7007750)
  17. Yutaro Yamaguchi:
    Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity.
    Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pp. 562–569. (DOI: 10.1137/1.9781611973402.42)
Preprints
  1. Takumi Kano, Yutaro Yamaguchi:
    A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices.
    arXiv preprints, arXiv:2604.23169 (Link), 2026.
  2. Ryo Suzuki, Yutaro Yamaguchi:
    Approximate Maintenance of Maximum Subarray Sum in the Sliding Window Model.
    arXiv preprints, arXiv:2604.23168 (Link), 2026.
  3. Kristóf Bérczi, Viktor Csaplár, Yutaro Yamaguchi:
    A Hierarchy of Edge-Weight Symmetries in Perfect Matchings.
    arXiv preprints, arXiv:2604.20009 (Link), 2026.
  4. Daisuke Shibatani, Yutaro Yamaguchi:
    Envy-Free School Redistricting Between Two Groups.
    arXiv preprints, arXiv:2603.19701 (Link), 2026.
  5. Shinnosuke Uba, Yutaro Yamaguchi:
    Regret Analysis of Sleeping Competing Bandits.
    arXiv preprints, arXiv:2603.19700 (Link), 2026.
  6. Takashi Horiyama, Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Akira Suzuki, Ryuhei Uehara, Yutaro Yamaguchi:
    Computational Complexity of Swish.
    arXiv preprints, arXiv:2601.09289 (Link), 2026.
  7. Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi:
    Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation.
    arXiv preprints, arXiv:2511.08210 (Link), 2025.
  8. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    The Rainbow Arborescence Problem on Cycles.
    arXiv preprints, arXiv:2511.04953 (Link), 2025.
    * This has been merged into arXiv:2412.15457 (Link).
  9. Florian Hörsch, Csaba Király, Mirabel Mendoza-Cadena, Gyula Pap, Eszter Szabó, Yutaro Yamaguchi:
    Odd and Even Harder Problems on Cycle-Factors.
    arXiv preprints, arXiv:2510.18393 (Link), 2025.
  10. Ryotaro Sato, Yutaro Yamaguchi:
    Exact Matching in Matrix Multiplication Time.
    arXiv preprints, arXiv:2508.04081 (Link), 2025.
  11. Yasuaki Kobayashi, Kazuhiro Kurita, Yutaro Yamaguchi:
    Finding One Local Optimum Is Easy — but What About Two?
    arXiv preprints, arXiv:2507.07524 (Link), 2025.
  12. Hiroki Shibata, Yuto Nakashima, Yutaro Yamaguchi, Shunsuke Inenaga:
    LZBE: An LZ-style Compressor Supporting O(log n)-Time Random Access.
    arXiv preprints, arXiv:2506.20107 (Link), 2025.
    * A preliminary version was entitled LZSE: An LZ-style Compressor Supporting O(log n)-Time Random Access.
  13. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Rainbow Arborescence Conjecture.
    arXiv preprints, arXiv:2412.15457 (Link), 2024.
    * This also appeared as an EGRES Technical Report, TR-2024-15 (Link).
  14. Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, Yutaro Yamaguchi:
    Towards the Proximity Conjecture on Group-Labeled Matroids.
    arXiv preprints, arXiv:2411.06771 (Link), 2024.
    * This also appeared as an EGRES Technical Report, TR-2024-06 (Link).
  15. Mihály Bárász, Kristóf Bérczi, Tamás Király, Taihei Oki, Yutaro Yamaguchi, Yu Yokoi:
    Matroid Intersection under Minimum Rank Oracle.
    arXiv preprints, arXiv:2407.03229 (Link), 2024.
    * A preliminary version also appeared as an EGRES Technical Report, TR-2024-13 (Link).
  16. Kristóf Bérczi, Tamás Király, Yusuke Kobayashi, Yutaro Yamaguchi, Yu Yokoi:
    Finding Spanning Trees with Perfect Matchings.
    arXiv preprints, arXiv:2407.02958 (Link), 2024.
    * This also appeared as an EGRES Technical Report, TR-2024-14 (Link).
  17. Hitoshi Murakami, Yutaro Yamaguchi:
    An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems.
    arXiv preprints, arXiv:2405.02829 (Link), 2024.
  18. Ryoma Norose, Yutaro Yamaguchi:
    Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs.
    arXiv preprints, arXiv:2404.17927 (Link), 2024.
  19. Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi:
    A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching.
    arXiv preprints, arXiv:2311.04140 (Link), 2023.
    * A preliminary version was entitled A Nearly Linear-Time Distributed Algorithm for Exact Maximum Matching.
  20. Alpár Jüttner, Csaba Király, Lydia Mirabel Mendoza-Cadena, Gyula Pap, Ildikó Schlotter, Yutaro Yamaguchi:
    Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions.
    arXiv preprints, arXiv:2308.12653 (Link), 2023.
  21. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Matroid Intersection under Restricted Oracles.
    arXiv preprints, arXiv:2209.14516 (Link), 2022.
  22. Kohei Morita, Shinya Shiroshita, Yutaro Yamaguchi, Yu Yokoi:
    Fast Primal-Dual Update against Local Weight Update in Linear Assignment Problem and Its Application.
    arXiv preprints, arXiv:2208.11325 (Link), 2022.
    * A preliminary version was entitled Maintaining Optimality in Assignment Problem against Weight Updates around Vertices.
  23. Kristóf Bérczi, Tamás Király, Tamás Schwarcz, Yutaro Yamaguchi, Yu Yokoi:
    Hypergraph Characterization of Split Matroids.
    arXiv preprints, arXiv:2202.04371 (Link), 2022.
    * This also appeared as an EGRES Technical Report, TR-2022-07 (Link).
  24. Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama, Jun Kawahara, Ichigaku Takigawa, Yutaro Yamaguchi:
    Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions.
    arXiv preprints, arXiv:2201.08118 (Link), 2022.
  25. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems.
    arXiv preprints, arXiv:2107.09897 (Link), 2021.
    * This also appeared as an EGRES Technical Report, TR-2021-08 (Link).
  26. Yuya Masumura, Taihei Oki, Yutaro Yamaguchi:
    Dynamic Programming Approach to the Generalized Minimum Manhattan Network Problem.
    arXiv preprints, arXiv:2004.11166 (Link), 2020.
  27. Kristóf Bérczi, Tamás Schwarcz, Yutaro Yamaguchi:
    List Coloring of Two Matroids through Reduction to Partition Matroids.
    arXiv preprints, arXiv:1911.10485 (Link), 2019.
    * This also appeared as an EGRES Technical Report, TR-2020-10 (Link).
  28. Takanori Maehara, So Nakashima, Yutaro Yamaguchi:
    Multiple Knapsack-Constrained Monotone DR-Submodular Maximization on Distributive Lattice — Continuous Greedy Algorithm on Median Complex —.
    arXiv preprints, arXiv:1907.04279 (Link), 2019.
  29. Takanori Maehara, Yutaro Yamaguchi:
    Stochastic Monotone Submodular Maximization with Queries.
    arXiv preprints, arXiv:1907.04083 (Link), 2019.
  30. Yoichi Iwata, Yutaro Yamaguchi:
    Finding a Shortest Non-zero Path in Group-Labeled Graphs.
    arXiv preprints, arXiv:1906.04062 (Link), 2019.
    * A preliminary version was entitled A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs.
  31. Yuval Filmus, Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi:
    Tight Approximation for Unconstrained XOS Maximization.
    arXiv preprints, arXiv:1811.09045 (Link), 2018.
  32. Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi:
    Subgame Perfect Equilibria of Sequential Matching Games.
    arXiv preprints, arXiv:1804.10353 (Link), 2018.
    * A preliminary version was entitled Computing a Subgame Perfect Equilibrium of a Sequential Matching Game.
  33. Takanori Maehara, Yutaro Yamaguchi:
    Stochastic Packing Integer Programs with Few Queries.
    arXiv preprints, arXiv:1707.04020 (Link), 2017.
  34. Yasushi Kawase, Yutaro Yamaguchi:
    Antimatroids Induced by Matchings.
    arXiv preprints, arXiv:1705.05510 (Link), 2017.
  35. Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida:
    0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms.
    arXiv preprints, arXiv:1704.02700 (Link), 2017.
    * A preliminary version was entitled Linear-Time FPT Algorithms via Half-Integral Non-returning A-path Packing.
  36. Kristóf Bérczi, Satoru Iwata, Jun Kato, Yutaro Yamaguchi:
    Making Bipartite Graphs DM-irreducible.
    arXiv preprints, arXiv:1612.08828 (Link), 2016.
    * A preliminary version had appeared as a Mathematical Engineering Technical Report, METR 2016-14 (Link).
  37. Yoshinobu Kawahara, Yutaro Yamaguchi:
    Parametric Maxflows for Structured Sparse Learning with Convex Relaxations of Submodular Functions.
    arXiv preprints, arXiv:1509.03946 (Link), 2015.
  38. Yutaro Yamaguchi:
    Shortest Disjoint Non-zero A-paths via Weighted Matroid Matching.
    Mathematical Engineering Technical Reports, METR 2015-20 (Link), Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2015.
  39. Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi:
    Finding a Path with Two Labels Forbidden in Group-Labeled Graphs.
    arXiv preprints, arXiv:1807.00109 (Link), 2018.
    * A preliminary version, entitled Finding a Path in Group-Labeled Graphs with Two Labels Forbidden, had appeared in 2014 as a Mathematical Engineering Technical Report, METR 2014-41 (Link).
  40. Yutaro Yamaguchi:
    Realizing Symmetric Set Functions as Hypergraph Cut Capacity.
    Mathematical Engineering Technical Reports, METR 2014-28 (Link), Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2014.
  41. Yutaro Yamaguchi, Anna Ogawa, Akiko Takeda, Satoru Iwata:
    Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms.
    Mathematical Engineering Technical Reports, METR 2014-12 (Link), Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2014.
  42. Yutaro Yamaguchi:
    Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity.
    Mathematical Engineering Technical Reports, METR 2013-35 (Link), Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2013.
  43. Shin-ichi Tanigawa, Yutaro Yamaguchi:
    Packing Non-zero A-paths via Matroid Matching.
    Mathematical Engineering Technical Reports, METR 2013-08 (Link), Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, Japan, 2013.
Theses

[Ph.D. Thesis] Combinatorial Optimization on Group-Labeled Graphs. (Supervised by Prof. Satoru Iwata)
Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Japan, March 2016.

[Master's Thesis] Structures and Algorithms for Path-Packing Problems. (Supervised by Prof. Satoru Iwata)
Department of Mathematical Sciences, Graduate School of Science, Kyoto University, Japan, January 2013.

Others
  1. Hiroki Shibata, Yuto Nakashima, Yutaro Yamaguchi, Shunsuke Inenaga:
    LZSE: An LZ-style Compressor Supporting O(log n)-Time Random Access.
    Proceedings of the 25th Japan–Korea Joint Workshop on Algorithms and Computation (WAAC 2025), 6pp.
  2. Ryotaro Sato, Yutaro Yamaguchi:
    Exact Matching in Matrix Multiplication Time.
    Proceedings of the 13th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 483–490, 2025.
  3. Kazuhiro Inaba, Ryoma Sin'ya, Yoshiki Nakamura, Yutaro Yamaguchi:
    Computational Complexity on Measureability of Alphabet-Testable, Piecewise-Testable, and Generalized-Definite Languages.
    Proceedings of the 26th Workshop on Programming and Programming Languages (PPL 2024).
    * This article is written in Japanese, and the English title is informal.
  4. Ryoma Sin'ya, Yutaro Yamaguchi, Yoshiki Nakamura:
    On Regular Languages Approximable by Testing Appearance of Subwords.
    Computer Software, 40:2 (2023), pp. 49–60. (DOI: 10.11309/jssst.40.2_49).
    * This article is written in Japanese except for the abstract, and the English title is informal.
  5. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Matroid Intersection under Restricted Oracles.
    Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 59–62, 2023.
  6. Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama, Jun Kawahara, Ichigaku Takigawa, Yutaro Yamaguchi:
    A ZDD-Based Method for Exactly Enumerating All Lower-Cost Solutions of Combinatorial Problems.
    Proceedings of the 5th Workshop on Enumeration Problems and Applications (WEPA 2022), 3pp.
  7. Ryoma Sin'ya, Yutaro Yamaguchi, Yoshiki Nakamura:
    On Regular Languages Approximable by Testing Appearance of Subwords.
    Proceedings of the 24th Workshop on Programming and Programming Languages (PPL 2022).
    * This article is written in Japanese, and the English title is informal.
  8. Takanori Maehara, Yutaro Yamaguchi:
    A Unified Framework for Combinatorial Optimization with Queries.
    Bulletin of the Japan Society for Industrial and Applied Mathematics, 29:2, pp. 2–9, 2019.
    * This article is written in Japanese except for the abstract, and the English title is informal.
  9. Yutaro Yamaguchi:
    An Efficient Dijkstra-Like Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs.
    Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 479–485, 2019.
  10. Takanori Maehara, Yutaro Yamaguchi:
    Stochastic Monotone Submodular Maximization with Queries.
    Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 46–56, 2019.
  11. Yusuke Kobayashi, Yutaro Yamaguchi:
    On Applications of Weighted Linear Matroid Parity.
    Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 363–372, 2017.
  12. Ryohei Fujimaki, Yutaro Yamaguchi, Riki Eto:
    Piecewise Sparse Linear Classification via Factorized Asymptotic Bayesian Inference.
    Transactions of the Japanese Society for Artificial Intelligence, 31:6 (2016), No. AI30-I_1-9 (Link).
    * This article is written in Japanese except for the title and abstract.
  13. Yutaro Yamaguchi:
    Realizing Symmetric Set Functions as Hypergraph Cut Capacity.
    Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 137–146, 2015.
  14. Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi:
    Finding a Zero Path in Z3-Labeled Graphs.
    RIMS Kokyuroku "Optimization Algorithms: Theory, Application and Implementation," No. 1931, pp. 148–160 (Link), Research Institute for Mathematical Sciences (RIMS), Kyoto University, Japan, 2015.
    * This is a resume of the technical report METR 2014-41.
  15. Yutaro Yamaguchi:
    Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity.
    RIMS Kokyuroku "Optimization: Theory and Application," No. 1879, pp. 157–163 (Link), Research Institute for Mathematical Sciences (RIMS), Kyoto University, Japan, 2014.
    * This is a resume of the same-title paper in SODA 2014.
  16. Yutaro Yamaguchi:
    Packing A-paths in Group-Labelled Graphs via Matroid Matching.
    Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 495–503, 2013.
International Talks
  1. Takashi Horiyama, Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Akira Suzuki, Ryuhei Uehara, Yutaro Yamaguchi:
    Computational Complexity of Swish Is Solved.
    The 13th International Conference on Fun With Algorithms (FUN 2026), Porquerolles, France, May 2026. (Slide)
  2. Ryotaro Sato, Yutaro Yamaguchi:
    Exact Matching in Matrix Multiplication Time.
    The 13th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, Japan, May 2025. (Slide)
  3. Yutaro Yamaguchi:
    Fast Algorithms for Finding a Maximum Matching: Centralized and Distributed. (Invited)
    The 6th Workshop on Enumeration Problems and Applications (WEPA 2024), Tochigi, Japan, October 2024. (Slide)
  4. Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi:
    Matroid Intersection under Restricted Oracles. (Invited)
    The 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, Hungary, March 2023. (Slide)
  5. Yutaro Yamaguchi:
    A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs.
    The 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, Utah, U.S., January 2020. (Slide)
  6. Yutaro Yamaguchi:
    An Efficient Dijkstra-Like Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs.
    The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, Japan, May 2019. (Slide)
  7. Kristóf Bérczi, Satoru Iwata, Jun Kato, Yutaro Yamaguchi:
    Making Bipartite Graphs DM-irreducible.
    The 23rd International Symposium on Mathematical Programming (ISMP 2018), Bordeaux, France, July 2018. (Slide)
  8. Yusuke Kobayashi, Yutaro Yamaguchi:
    On Applications of Weighted Linear Matroid Parity.
    The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Budapest, Hungary, May 2017. (Slide)
  9. Yutaro Yamaguchi:
    Shortest Disjoint S-paths via Weighted Linear Matroid Parity.
    The 27th International Symposium on Algorithms and Computation (ISAAC 2016), Sydney, Australia, December 2016. (Slide)
  10. Satoru Iwata, Jun Kato, Yutaro Yamaguchi:
    How to Make a Bipartite Graph DM-irreducible by Adding Edges.
    The Japanese Conference on Combinatorics and its Applications (JCCA 2016), Kyoto, Japan, May 2016. (Slide)
  11. Satoru Iwata, Jun Kato, Yutaro Yamaguchi:
    How to Make a Bipartite Graph DM-irreducible by Adding Edges.
    NII Shonan Meeting Seminar 071 "Current Trend in Combinatorial Optimization," Kanagawa, Japan, April 2016. (Slide)
  12. Yutaro Yamaguchi:
    Packing Non-zero A-paths via Linear Matroid Parity.
    The 6th Cargèse Workshop on Combinatorial Optimization, Cargèse, Corsica, France, September 2015. (Slide)
  13. Shin-ichi Tanigawa, Yutaro Yamaguchi:
    Packing Non-zero A-paths via Matroid Matching.
    The 22nd International Symposium on Mathematical Programming (ISMP 2015), Pittsburgh, Pennsylvania, U.S., July 2015. (Slide)
  14. Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi:
    Finding a Path in Group-Labeled Graphs with Two Labels Forbidden.
    The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, July 2015. (Slide)
  15. Yutaro Yamaguchi:
    Realizing Symmetric Set Functions as Hypergraph Cut Capacity.
    The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Fukuoka, Japan, June 2015. (Slide)
  16. Yutaro Yamaguchi:
    Packing A-paths in Group-Labeled Graphs via Linear Matroid Parity.
    IMA Annual Program Year Workshop "Convexity and Optimization: Theory and Applications," Minneapolis, Minnesota, U.S., February 2015. (Poster, Summary)
  17. Yutaro Yamaguchi, Anna Ogawa, Akiko Takeda, Satoru Iwata:
    Cyber Security Analysis of Power Networks by Hypergraph Cut Algorithms.
    The 5th IEEE International Conference on Smart Grid Communications (SmartGridComm 2014), Venice, Italy, November 2014. (Slide)
  18. Yutaro Yamaguchi:
    Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity.
    The 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, Oregon, U.S., January 2014. (Slide)
  19. Yutaro Yamaguchi:
    Packing A-paths in Group-Labelled Graphs via Matroid Matching.
    The 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Veszprém, Hungary, June 2013.
Visited Cities
  1. Porquerolles in France: May 2026.
    Talk in the 13th International Conference on Fun With Algorithms (FUN 2026).
  2. Velence in Hungary: July 2025.
    The 17th Emléktábla Workshop.
  3. Vác in Hungary: July 2024.
    The 16th Emléktábla Workshop.
  4. Alexandria in Virginia, U.S.: January 2024.
    The 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024).
  5. München (Munich) in Germany, Wien (Vienna) in Austria, and Praha (Prague) and Plzeň (Pilsen) in Czech Republic: September – October 2023.
    Private Visit.
  6. Szentendre in Hungary, Bruxelles (Brussels) in Belgium, and London and Oxford in U.K.: March – May 2023.
    Private Visits (Weekend Trips).
  7. Gárdony (+ Mislolc) in Hungary: July 2022.
    The 12th Emléktábla Workshop.
  8. Salt Lake City in Utah, U.S.: January 2020.
    Talk in the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).
  9. Eger, Tokaj, Visegrad, and Szeged in Hungary, Wien (Vienna) in Austria, Praha (Prague) in Czech Republic, Dubrovnik in Croatia, and Bratislava in Slovakia: October – November 2019.
    Private Visits (Weekend Trips).
  10. Bordeaux in France: July 2018.
    Talk in the 23rd International Symposium on Mathematical Programming (ISMP 2018).
  11. Ithaca in New York, U.S.: June 2018.
    The 19th ACM Conference on Economics and Computation (EC 2018).
  12. New Orleans in Louisiana, U.S.: January 2018.
    The 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
  13. Barcelona in Spain: January 2017.
    The 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).
  14. Sydney in Australia: December 2016.
    Talk in the 27th International Symposium on Algorithms and Computation (ISAAC 2016).
  15. Arlington in Virginia, U.S.: January 2016.
    The 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016).
  16. Bonn (+ Frankfurt, Stuttgart, München (Munich), Köln, and Mainz) in Germany: October 2015.
    HIM Trimester Program "Combinatorial Optimization," Rigidity Workshop.
  17. Cargèse in Corsica (+ Paris) in France: September 2015.
    Talk in the 6th Cargèse Workshop on Combinatorial Optimization.
  18. Seattle in Washington, U.S.: August 2015.
    Private Visit.
  19. Pittsburgh in Pennsylvania, U.S.: July 2015.
    Talk in the 22nd International Symposium on Mathematical Programming (ISMP 2015).
  20. Minneapolis in Minnesota, U.S.: February 2015.
    IMA Annual Program Year Workshop "Convexity and Optimization: Theory and Applications."
  21. Venezia (Venice) in Italy: November 2014.
    Talk in the 5th IEEE International Conference on Smart Grid Communications (SmartGridComm 2014).
  22. Budapest in Hungary:
  23. Silicon Valley (San Jose, Mountain View, and Cupertino) and San Francisco (+ Yosemite Park) in California, U.S.: February – March 2014.
    Joint Research to NEC Laboratories America at Cupertino.
  24. Portland in Oregon, U.S.: January 2014.
    Talk in the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).
  25. Veszprém in Hungary: June 2013.
    Talk in the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications.
  26. Zurich and Engelberg in Switzerland: March 2012.
    The 1st ETH-Japan Symposium for the Promotion of Academic Exchanges and the 1st ETH-Japan Workshop on Science and Computing.
  27. Toronto and Waterloo in Canada: September 2011.
    Invited to a special program on Quantum Computing at Institute for Quantum Computing (IQC) in University of Waterloo.