Yusuke Kobayashi
Research Institute for Mathematical Sciences,
Kyoto University,
Kyoto 606-8502, Japan.

Email:Web:

yusuke@kurims.kyoto-u.ac.jp
http://www.kurims.kyoto-u.ac.jp/∼yusuke/

Personal
Born on August 2, 1982.
Japanese Citizen.

Research Interests
Graph algorithm, discrete structure, combinatorial optimization, and graph theory.

Education
Bachelor of Engineering from Faculty of Engineering, University of Tokyo, March 2005.
Master of Information Science and Technology from Graduate School of Information Science and Technology, University of Tokyo, March 2007.
Ph.D in Information Science and Technology from Graduate School of Information Science and Technology, University of Tokyo, March 2010.
Dissertation Title: Algorithms for Finding Disjoint Paths: Acceleration and Extension
Adviser: Professor Kazuo Murota

Academic Appointments
Research Fellow of the Japan Society for the Promotion of Science (DC1), April 2007–March 2010.
Assistant Professor at University of Tokyo, April 2010–March 2015.
Associate Professor at University of Tsukuba, April 2015–March 2018.
Associate Professor at Kyoto University, April 2018–present.

Publications
Journal Articles
1. Y. Kobayashi, K. Murota, and K. Tanaka: Operations on M-convex functions on jump systems, SIAM
Journal on Discrete Mathematics, 21 (2007), pp. 107–129.
2. Y. Kobayashi and K. Murota: Induction of M-convex functions by linking systems, Discrete Applied
Mathematics, 155 (2007), pp. 1471–1480.

Yusuke Kobayashi

2

3. Y. Kobayashi and K. Takazawa: Even factors, jump systems, and discrete convexity, Journal of Combinatorial Theory, Series B, 99 (2009), pp. 139–161.
4. Y. Kobayashi: Induced disjoint paths problem in a planar digraph, Discrete Applied Mathematics, 157(2009), pp. 3231–3238.
5. S. Iwata and Y. Kobayashi: An algorithm for minimum cost arc-connectivity orientations, Algorithmica,
56 (2010), pp. 437–447.
6. Y. Kobayashi: A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs,
Discrete Optimization, 7 (2010), pp. 197–202.
7. Y. Kobayashi and C. Sommer: On shortest disjoint paths in planar graphs, Discrete Optimization, 7(2010), pp. 234–245.
8. K. Kawarabayashi and Y. Kobayashi: Algorithms for finding an induced cycle in planar graphs, Combinatorica, 30 (2010), pp. 715–734.
9. K. Kawarabayashi and Y. Kobayashi: An improved algorithm for the half-disjoint paths problem,
SIAM Journal on Discrete Mathematics, 25 (2011), pp. 1322–1330.
10. S. Imahori, Y. Miyamoto, H. Hashimoto, Y. Kobayashi, M. Sasaki, and M. Yagiura: The complexityof the node capacitated in-tree packing problem, Networks, 59 (2012), pp. 13–21.
11. K. Kawarabayashi, Y. Kobayashi, and B. Reed: The disjoint paths problem in quadratic time, Journalof Combinatorial Theory, Series B, 102 (2012), pp. 424–435.
12. K. Bérczi and Y. Kobayashi: An algorithm for (n − 3)-connectivity augmentation problem: jumpsystem approach, Journal of Combinatorial Theory, Series B, 102 (2012), pp. 565–587.
13. K. Kawarabayashi and Y. Kobayashi: A linear time algorithm for the induced disjoint paths problem
in planar graphs, Journal of Computer and System Sciences, 78 (2012), pp. 670–680.
14. K. Kawarabayashi and Y. Kobayashi: An immersion of a square in 4-edge-connected graphs, Progressin Informatics, 9 (2012), pp. 35–36.
15. Y. Yoshida and Y. Kobayashi: Testing the (s, t)-disconnectivity of graphs and digraphs, TheoreticalComputer Science, 434 (2012), pp. 98–113.
16. Y. Kobayashi and X. Yin: An algorithm for finding a maximum t-matching excluding complete partite
subgraphs, Discrete Optimization, 9 (2012), pp. 98–108.
17. Y. Kobayashi and Y. Yoshida: Algorithms for finding a maximum non-k-linked graph, SIAM Journal
on Discrete Mathematics, 26 (2012), pp. 591–604.
18. Y. Kobayashi, J. Szabó, and K. Takazawa: A proof of Cunningham’s conjecture on restricted subgraphs
and jump systems, Journal of Combinatorial Theory, Series B, 102 (2012), pp. 948–966.
19. K. Kawarabayashi and Y. Kobayashi: Fixed-parameter tractability for the subset feedback set problem
and the S-cycle packing problem, Journal of Combinatorial Theory, Series B, 102 (2012), pp. 1020–
1034.
20. Y. Kobayashi, K. Murota, and R. Weismantel: Cone superadditivity of discrete convex functions,
Mathematical Programming, Series A, 135 (2012), pp. 25–44.
21. K. Kawarabayashi and Y. Kobayashi: An O(log n)-approximation algorithm for the edge-disjoint paths
problem in Eulerian planar graphs, ACM Transactions on Algorithms, 9 (2013), Article 16.

Yusuke Kobayashi

3

22. R. Fujita, Y. Kobayashi, and K. Makino: Robust matchings and matroid intersections, SIAM Journal
on Discrete Mathematics, 27 (2013), pp. 1234–1256.
23. Y. Kobayashi: Triangle-free 2-matchings and M-concave functions on jump systems, Discrete Applied
Mathematics, 175 (2014), pp. 35–42.
24. A. Kawamura and Y. Kobayashi: Fence patrolling by mobile agents with distinct speeds, Distributed
Computing, 28 (2015), pp. 147–154.
25. H. Flier, Y. Kobayashi, M. Mihalák, A. Schöbel, P. Widmayer, and A. Zych, Selecting vertex disjoint
paths in plane graphs, Networks, 66 (2015), pp. 136–144.
26. K. Kawarabayashi and Y. Kobayashi: The edge disjoint paths problem in Eulerian graphs and 4-edgeconnected graphs, Combinatorica, 35 (2015), pp. 477–495.
27. Y. Kobayashi: The complexity of minimizing the difference of two M\ -convex set functions, Operations
Research Letters, 43 (2015), pp. 573–574.
28. K. Ishihara and Y. Kobayashi: Routing algorithms under mutual interference constraints, Journal of
the Operations Research Society of Japan, 58 (2015), pp. 209–222.
29. A. Bernáth, Y. Kobayashi, and T. Matsuoka: The generalized terminal backup problem, SIAM Journal
on Discrete Mathematics, 29 (2015), pp. 1764–1782.
30. K. Otsuki, Y. Kobayashi, and K. Murota: Improved max-flow min-cut algorithms in a circular disk
failure model with application to a road network, European Journal of Operational Research, 248(2016), pp. 396–403.
31. K. Kawarabayashi and Y. Kobayashi: Edge-disjoint odd cycles in 4-edge-connected graphs, Journal of
Combinatorial Theory, Series B, 119 (2016), pp. 12–27.
32. K. Bérczi, T. Király, and Y. Kobayashi: Covering intersecting bi-set families under matroid constraints,
SIAM Journal on Discrete Mathematics, 30 (2016), pp. 1758–1774.
33. K. Kawarabayashi and Y. Kobayashi: An improved approximation algorithm for the edge-disjoint
paths problem with congestion two, ACM Transactions on Algorithms, 13 (2016), Article 5.
34. Y. Kobayashi and S. Toyooka: Finding a shortest non-zero path in group-labeled graphs via permanentcomputation, Algorithmica, 77 (2017), pp. 1128–1142.
35. N. Kakimura, K. Kawarabayashi, and Y. Kobayashi: Packing edge-disjoint odd Eulerian subgraphs
through prescribed vertices in 4-edge-connected graphs, SIAM Journal on Discrete Mathematics, 31(2017), pp. 766–782.
36. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Efficient stabilization of cooperative matching games, Theoretical Computer Science, 677 (2017), pp. 69–82.
37. K. Bérczi and Y. Kobayashi: An algorithm for identifying cycle-plus-triangles graphs, Discrete Applied
Mathematics, 226 (2017), pp. 10–16.
38. Y. Kobayashi and K. Takazawa: Randomized strategies for cardinality robustness in the knapsackproblem, Theoretical Computer Science, 699 (2017), pp. 53–62.
39. H. Nishiyama, Y. Kobayashi, Y. Yamauchi, S. Kijima, and M. Yamashita: The parity Hamiltonian
cycle problem, Discrete Mathematics, 341 (2018), pp. 606–626.

Yusuke Kobayashi

4

40. T. N. Hau, N. Kakimura, K. Kawarabayashi, Y. Kobayashi, T. Matsuoka, and Y. Yokoi: Optimal cache
placement for an academic backbone network, Journal of the Operations Research Society of Japan, 61(2018), pp. 197–216.
41. K. Kawarabayashi and Y. Kobayashi: All-or-nothing multicommodity flow problem with bounded
fractionality in planar graphs, SIAM Journal on Computing, 47 (2018), pp. 1483–1504.
42. Y. Kobayashi: NP-hardness and fixed-parameter tractability of the minimum spanner problem, Theoretical Computer Science, 746 (2018), pp. 88–97.
43. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Minimum-cost b-edge dominatingsets on trees, Algorithmica, 81 (2019), pp. 343–366.
44. Y. Kobayashi and R. Sako: Two disjoint shortest paths problem with non-negative edge length, Operations Research Letters, 47 (2019), pp. 66-69.
45. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Reconfiguration of maximumweight b-matchings in a graph, Journal of Combinatorial Optimization, 37 (2019), pp. 454–464.
46. K. Takayama and Y. Kobayashi: A strongly polynomial time algorithm for the maximum supply rate
problem on trees, Theoretical Computer Science, 806 (2020), pp. 323–331.
47. K. Kawarabayashi and Y. Kobayashi: Linear min-max relation between the treewidth of an H-minorfree graph and its largest grid minor, Journal of Combinatorial Theory, Series B, 141 (2020), pp. 165–
180.
48. Y. Kawase, Y. Kobayashi, and Y. Yamaguchi: Finding a path with two labels forbidden in grouplabeled graphs, Journal of Combinatorial Theory, Series B, 143 (2020), pp. 65–122.
49. H.L. Bodlaender, T. Hanaka, Y. Kobayashi, Y. Kobayashi, Y. Okamoto, Y. Otachi, and T.C. van derZanden: Subgraph isomorphism on graph classes that exclude a substructure, Algorithmica, 82 (2020),
pp. 3566–3587.
50. K. Takayama and Y. Kobayashi: On the number of edges in a graph with many two-hop disjoint paths,
Discrete Applied Mathematics, 283 (2020), pp. 718–723.
51. M. Bonamy, M. Heinrich, T. Ito, Y. Kobayashi, H. Mizuta, M. Mühlenthaler, A. Suzuki, and K. Wasa:
Diameter of colorings under Kempe changes, Theoretical Computer Science, 838 (2020), pp. 45–57.
52. T. Ito, N. Kakimura, and Y. Kobayashi: Complexity of the multi-service center problem, TheoreticalComputer Science, 842 (2020), pp. 18–27.
53. G.L. Duarte, H. Eto, T. Hanaka, Y. Kobayashi, Y. Kobayashi, D. Lokshtanov, L.L.C. Pedrosa, R.C.S.
Schouery, U.S. Souza: Computing the largest bond and the maximum connected cut of a graph,
Algorithmica, 83 (2021), pp. 1421–1458.
54. T. Hanaka, Y. Kobayashi, Y. Kobayashi, and T. Yagita: Finding a maximum minimal separator: graphclasses and fixed-parameter tractability, Theoretical Computer Science, 865 (2021), pp. 131–140.
55. T. Ito, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Algorithms for gerrymandering over graphs,
Theoretical Computer Science, 868 (2021), pp. 30–45.
56. Y. Iwata and Y. Kobayashi: Improved analysis of highest-degree branching for feedback vertex set,
Algorithmica, 83 (2021), pp. 2503–2520.
57. Y. Filmus, Y. Kawase, Y. Kobayashi, and Y. Yamaguchi: Tight approximation for unconstrained XOS
maximization, Mathematics of Operations Research, 46 (2021), pp. 1599–1610.

Yusuke Kobayashi

5

58. K. Bérczi, N. Kakimura, and Y. Kobayashi: Market pricing for matroid rank valuations, SIAM Journal
on Discrete Mathematics, 35 (2021), pp. 2662–2678.
59. R. Belmonte, T. Hanaka, M. Kanzaki, M. Kiyomi, Y. Kobayashi, Y. Kobayashi, M. Lampis, H. Ono,and Y. Otachi: Parameterized complexity of (A, `)-path packing, Algorithmica, 84 (2022), pp. 871–895.
60. Y. Kobayashi, Y. Okamoto, Y. Otachi, and Y. Uno: Linear-time recognition of double-threshold graphs,
Algorithmica, 84 (2022), pp. 1163–1181.
61. Y. Kobayashi: Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles, Mathematical Programming, Series B, 192 (2022), pp. 675–702.
62. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Shortest reconfiguration of perfectmatchings via alternating cycles, SIAM Journal on Discrete Mathematics, 36 (2022), pp. 1102–1123.
63. S. Iwata and Y. Kobayashi: A weighted linear matroid parity algorithm, SIAM Journal on Computing,51 (2022), pp. STOC17-238–STOC17-280.
64. Y. Aoike, T. Gima, T. Hanaka, M. Kiyomi, Y. Kobayashi, Y. Kobayashi, K. Kurita, and Y. Otachi:
An improved deterministic parameterized algorithm for cactus vertex deletion, Theory of Computing
Systems, 66 (2022), pp. 502–515.
65. N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Submodular reassignment problem forreallocating agents to tasks with synergy effects, Discrete Optimization, 44 (2022), 100631.
66. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, Y. Okamoto: A parameterized view to the robust
recoverable base problem of matroids under structural uncertainty, Operations Research Letters, 50(2022), pp. 370–375.
67. T. Ishii, A. Kawamura, Y. Kobayashi, and K. Makino: Trade-offs among degree, diameter, and numberof paths, Discrete Applied Mathematics, 327 (2023), pp. 96–100.
68. Y. Kobayashi and R. Mahara: Approximation algorithm for Steiner tree problem with neighbor-induced
cost, Journal of the Operations Research Society of Japan, 66 (2023), pp. 18–36.
69. T. Ito, Y. Iwamasa, N. Kakimura, N. Kamiyama, Y. Kobayashi, S. Maezawa, Y. Nozaki, Y. Okamoto,and K. Ozeki: Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams,
ACM Transactions on Algorithms, 19 (2023), Article 6.
70. N. Bousquet, T. Ito, Y. Kobayashi, H. Mizuta, P. Ouvrard, A. Suzuki, and K. Wasa: Reconfiguration of
spanning trees with degree constraints or diameter constraints, Algorithmica, 85 (2023), pp. 2779–2816.
71. T. Hatanaka, F. Hommelsheim, T. Ito, Y. Kobayashi, M. Mühlenthaler, and A. Suzuki: Fixedparameter algorithms for graph constraint logic, Theoretical Computer Science, 959 (2023), 113863.
72. N. Bousquet, F. Hommelsheim, Y. Kobayashi, M. Mühlenthaler, and A. Suzuki: Feedback vertex set
reconfiguration in planar graphs, Theoretical Computer Science, 979 (2023), 114188.
73. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, Y. Nozaki, Y. Okamoto, and K. Ozeki: On reachable
assignments under dichotomous preferences, Theoretical Computer Science, 979 (2023), 114196.
74. K. Bérczi, E.R. Kovács, E. Boros, F.T. Gedefa, N. Kamiyama, T. Kavitha, Y. Kobayashi, and K.
Makino: Envy-free relaxations for goods, chores, and mixed items, Theoretical Computer Science, toappear.
75. Y. Kobayashi: Optimal general factor problem and jump system intersection, Mathematical Programming, Series B, to appear.

Yusuke Kobayashi

6

Refereed Conference Proceedings
1. K. Kawarabayashi and Y. Kobayashi: The induced disjoint paths problem, Proceedings of the 13th
Conference on Integer Programming and Combinatorial Optimization (IPCO 2008), LNCS 5035, 2008,
pp. 47–61.
2. Y. Kobayashi and K. Kawarabayashi: Algorithms for finding an induced cycle in planar graphs andbounded genus graphs, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA 2009), 2009, pp. 1146–1155.
3. S. Imahori, Y. Miyamoto, H. Hashimoto, Y. Kobayashi, M. Sasaki, and M. Yagiura: The complexity of
the node capacitated in-tree packing problem, Proceedings of the International Network Optimization
Conference 2009, 2009.
4. Y. Kobayashi and C. Sommer: On shortest disjoint paths in planar graphs, Proceedings of the 20th
International Symposium on Algorithms and Computation (ISAAC 2009), LNCS 5878, 2009, pp. 293–
302.
5. K. Kawarabayashi and Y. Kobayashi: The edge disjoint paths problem in Eulerian graphs and 4-edgeconnected graphs, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms(SODA 2010), 2010, pp. 345–353.
6. K. Kawarabayashi and Y. Kobayashi: An O(log n)-approximation algorithm for the disjoint paths
problem in Eulerian planar graphs and 4-edge-connected planar graphs, Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX
2010), LNCS 6302, 2010, pp. 274–286.
7. K. Kawarabayashi and Y. Kobayashi: Improved algorithm for the half-disjoint paths problem, Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization
Problems (APPROX 2010), LNCS 6302, 2010, pp. 287–297.
8. R. Fujita, Y. Kobayashi, and K. Makino: Robust matchings and matroid intersections, Proceedings ofthe 18th Annual European Symposium on Algorithms (ESA 2010), LNCS 6347, 2010, pp. 123–134.
9. K. Kawarabayashi and Y. Kobayashi: Breaking O(n1/2 )-approximation algorithms for the edge-disjoint
paths problem with congestion two, Proceedings of the 43rd ACM Symposium on Theory of Computing(STOC 2011), 2011, pp. 81–88.
10. Y. Kobayashi and Y. Yoshida: Algorithms for finding a maximum non-k-linked graph, Proceedings ofthe 19th European Symposium on Algorithms (ESA 2011), LNCS 6942, 2011, pp. 131–142.
11. N. Kakimura, K. Kawarabayashi, and Y. Kobayashi: Erdős-Pósa property and its algorithmic applications — parity constraints, subset feedback set, and subset packing, Proceedings of the 23rd Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 2012, pp. 1726–1736.
12. K. Kawarabayashi and Y. Kobayashi: List-coloring graphs without subdivisions and without immersions, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012),
2012, pp. 1425–1435.
13. K. Kawarabayashi and Y. Kobayashi: Edge-disjoint odd cycles in 4-edge-connected graphs, Proceedingsof the 29th Symposium on Theoretical Aspects of Computer Science (STACS 2012), 2012, pp. 206–217.
14. K. Kawarabayashi and Y. Kobayashi: Linear min-max relation between the treewidth of H-minorfree graphs and its largest grid minor, Proceedings of the 29th Symposium on Theoretical Aspects ofComputer Science (STACS 2012), 2012, pp. 278–289.

Yusuke Kobayashi

7

15. A. Kawamura and Y. Kobayashi: Fence patrolling by mobile agents with distinct speeds, Proceedingsof the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), LNCS 7676,
2012, pp. 598–608.
16. K. Kawarabayashi and Y. Kobayashi: All-or-nothing multicommodity flow problem with bounded
fractionality in planar graphs, Proceedings of the 54th Annual IEEE Symposium on Foundations ofComputer Science (FOCS 2013), 2013, pp. 187–196.
17. A. Bernáth and Y. Kobayashi: The generalized terminal backup problem, Proceedings of the 25th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 2014, pp. 1678–1686.
18. Y. Kobayashi and K. Otsuki: Max-flow min-cut theorem and faster algorithms in a circular disk failure
model, Proceedings of the 33rd Annual IEEE International Conference on Computer Communications(INFOCOM 2014), 2014, pp. 1635–1643.
19. K. Kawarabayashi, Y. Kobayashi, and S. Kreutzer: An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem, Proceedings of the 46th ACM Symposium on Theoryof Computing (STOC 2014), 2014, pp. 70–78.
20. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Minimum-cost b-edge dominatingsets on trees, Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC
2014), LNCS 8889, 2014, pp. 195–207.
21. Y. Kawase, Y. Kobayashi, and Y. 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), 2015, pp. 797–809.
22. Y. Kobayashi and K. Takazawa: Randomized strategies for cardinality robustness in the knapsackproblem, Proceedings of the 13th Meeting on Analytic Algorithmics and Combinatorics (ANALCO
2016), 2016, pp. 25-33.
23. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Efficient stabilization of cooperative matching games, Proceedings of the 15th International Conference on Autonomous Agents andMultiagent Systems (AAMAS 2016), 2016, pp. 41–49.
24. S. Iwata and Y. Kobayashi: A weighted linear matroid parity algorithm, Proceedings of the 49th ACM
Symposium on Theory of Computing (STOC 2017), 2017, pp. 264–276.
25. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Reconfiguration of maximumweight b-matchings in a graph, Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017), pp. 287–296.
26. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, Y. Okamoto, and T. Shiitada: Tight approximability of the server allocation problem for real-time applications, Proceedings of the 3rd International
Workshop on Algorithmic Aspects of Cloud Computing (Algocloud 2017), pp. 41–55.
27. K. Bérczi and Y. Kobayashi: The directed disjoint shortest paths problem, Proceedings of the 25th
European Symposium on Algorithms (ESA 2017), 13:1–13.13.
28. T. Ito, N. Kakimura, and Y. Kobayashi: Complexity of the multi-service center problem, Proceedingsof the 28th International Symposium on Algorithms and Computation (ISAAC 2017), 48:1–48:12.
29. K. Takayama and Y. Kobayashi: A strongly polynomial time algorithm for the maximum supply rate
problem on trees, Proceedings of the 12th International Frontiers of Algorithmics Workshop (FAW
2018), pp. 54–57.

Yusuke Kobayashi

8

30. T. Ito, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Algorithms for gerrymandering over graphs,
Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), pp. 1413–1421.
31. Y. Kobayashi, Y. Kobayashi, S. Miyazaki, and S. Tamaki: An improved fixed-parameter algorithm
for max-cut parameterized by crossing number, Proceedings of the 30th International Workshop on
Combinatorial Algorithms (IWOCA 2019), pp. 327–338.
32. M. Bonamy, M. Heinrich, T. Ito, Y. Kobayashi, H. Mizuta, M. Mühlenthaler, A. Suzuki, and K. Wasa:
Diameter of colorings under Kempe changes, Proceedings of the 25th Annual International Computing
and Combinatorics Conference (COCOON 2019), pp. 52–64.
33. M. Bonamy, N. Bousquet, M. Heinrich, T. Ito, Y. Kobayashi, A. Mary, M. Mühlenthaler, and K. Wasa:
The perfect matching reconfiguration problem, Proceedings of the 44th International Symposium on
Mathematical Foundations of Computer Science (MFCS 2019), 80:1–80:14.
34. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Shortest reconfiguration of
perfect matchings via alternating cycles, Proceedings of the 27th European Symposium on Algorithms(ESA 2019), 61:1–61:15.
35. H. Eto, T. Hanaka, Y. Kobayashi, and Y. Kobayashi: Parameterized algorithms for maximum cutwith connectivity constraints, Proceedings of the 14th International Symposium on Parameterized andExact Computation (IPEC 2019), 13:1–13:15.
36. Y. Iwata and Y. Kobayashi: Improved analysis of highest-degree branching for feedback vertex set,
Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC
2019), 22:1–22:11.
37. M. Bonamy, M. Heinrich, T. Ito, Y. Kobayashi, H. Mizuta, M. Mühlenthaler, A. Suzuki, and K. Wasa:
Shortest reconfiguration of colorings under Kempe-changes, Proceedings of the 37th Symposium on
Theoretical Aspects of Computer Science (STACS 2020), 2020, 35:1–35:14.
38. Y. Kobayashi: An FPT algorithm for minimum additive spanner problem, Proceedings of the 37th
Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, 11:1–11:16.
39. Y. Kobayashi: Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles, Proceedings of the 21st Conference on Integer Programming and Combinatorial Optimization (IPCO 2020),
2020, pp. 280–293.
40. T. Jordán, Y. Kobayashi, R. Mahara, and K. Makino: The Steiner problem for count matroids,
Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), pp. 330–
342.
41. R. Belmonte, T. Hanaka, M. Kanzaki, M. Kiyomi, Y. Kobayashi, Y. Kobayashi, M. Lampis, H. Ono,and Y. Otachi: Parameterized complexity of (A, `)-path packing, Proceedings of the 31st International
Workshop on Combinatorial Algorithms (IWOCA 2020), pp. 43–55.
42. Y. Kobayashi, Y. Okamoto, Y. Otachi, and Y. Uno: Linear-time recognition of double-threshold graphs,
Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science(WG 2020), pp. 286–297.
43. N. Bousquet, T. Ito, Y. Kobayashi, H. Mizuta, P. Ouvrard, A. Suzuki, and K. Wasa: Reconfigurationof spanning trees with many or few leaves, Proceedings of the 28th European Symposium on Algorithms(ESA 2020), 24:1–24:15.

Yusuke Kobayashi

9

44. K. Bérczi, N. Kakimura, and Y. Kobayashi: Market pricing for matroid rank valuations, Proceedingsof the 31st International Symposium on Algorithms and Computation (ISAAC 2020), 39:1–39:15.
45. T. Hatanaka, F. Hommelsheim, T. Ito, Y. Kobayashi, M. Mühlenthaler, and A. Suzuki: Fixedparameter algorithms for graph constraint logic, Proceedings of the 15th International Symposium
on Parameterized and Exact Computation (IPEC 2020), 15:1–15:15.
46. T. Ito, Y. Iwamasa, N. Kakimura, N. Kamiyama, Y. Kobayashi, S. Maezawa, Y. Nozaki, Y. Okamoto,and K. Ozeki: Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams,
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pp. 1342–1355.
47. N. Bousquet, T. Ito, Y. Kobayashi, H. Mizuta, P. Ouvrard, A. Suzuki, and K. Wasa: Reconfigurationof spanning trees with degree constraint or diameter constraint, Proceedings of the 39th International
Symposium on Theoretical Aspects of Computer Science (STACS 2022), 15:1–15:21.
48. T. Ito, Y. Iwamasa, N. Kakimura, N. Kamiyama, Y. Kobayashi, Y. Nozaki, Y. Okamoto, and K. Ozeki:
Reforming an envy-free matching, Proceedings of the 36th AAAI Conference on Artificial Intelligence(AAAI 2022), pp. 5084–5091.
49. A. Inoue and Y. Kobayashi: An additive approximation scheme for the Nash social welfare maximization with identical additive valuations, Proceedings of the 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022), pp. 341–354.
50. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, Y. Nozaki, Y. Okamoto, and K. Ozeki: On reachable assignments under dichotomous preferences, Proceedings of the 24th International Conference on
Principles and Practice of Multi-Agent Systems (PRIMA 2022), pp. 650–658.
51. Y. Kobayashi and T. Terao: One-face shortest disjoint paths with a deviation terminal, Proceedings ofthe 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 47:1–47:15.
52. Y. Kobayashi and R. Mahara: Proportional allocation of indivisible goods up to the least valued goodon average, Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC
2022), 55:1–55:13.
53. T. Hanaka, M. Kiyomi, Y. Kobayashi, Y. Kobayashi, K. Kurita, and Y. Otachi: A framework to design
approximation algorithms for finding diverse solutions in combinatorial problems, Proceedings of the37th AAAI Conference on Artificial Intelligence (AAAI 2023), pp. 3968–3976.
54. T. Ito, Y. Iwamasa, Y. Kobayashi, S. Maezawa, Y. Nozaki, Y. Okamoto, and K. Ozeki: Reconfiguration of colorings in triangulations of the sphere, Proceedings of the 39th International Symposium on
Computational Geometry (SoCG 2023), 43:1–43:16.
55. Y. Kobayashi: Optimal general factor problem and jump system intersection, Proceedings of the 24th
Conference on Integer Programming and Combinatorial Optimization (IPCO 2023), pp. 291–305.
56. T. Ito, Y. Iwamasa, N. Kakimura, Y. Kobayashi, S. Maezawa, Y. Nozaki, Y. Okamoto, and K. Ozeki:
Rerouting planar curves and disjoint paths, Proceedings of the 50th EATCS International Colloquium
on Automata, Languages and Programming (ICALP 2023), 81:1–81:19, 2023.
57. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, S. Maezawa, Y. Nozaki, and Y. Okamoto: Hardness of finding combinatorial shortest paths on graph associahedra, Proceedings of the 50th EATCS
International Colloquium on Automata, Languages and Programming (ICALP 2023), 82:1–82:17, 2023.
58. T. Ito, Y. Iwamasa, N. Kamiyama, Y. Kobayashi, Y. Kobayashi, S. Maezawa, and A. Suzuki: Reconfiguration of time-respecting arborescences, Proceedings of the 18th Algorithms and Data Structures
Symposium (WADS 2023), pp. 521–532.

Yusuke Kobayashi

10

59. T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto: Algorithmic theory of qubit
routing, Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023), pp. 533–
546.
60. Y. Kobayashi, R. Mahara, and Souta Sakamoto: EFX allocations for indivisible chores: matchingbased approach, Proceedings of the 16th International Symposium on Algorithmic Game Theory (SAGT2023), pp. 257–270.
61. Y. Kobayashi and T. Noguchi: An approximation algorithm for two-edge-connected subgraph problem
via triangle-free two-edge-cover, Proceedings of the 34th International Symposium on Algorithms andComputation (ISAAC 2023), 43:1–43:10, 2023.
62. Y. Kobayashi, R. Mahara, and T. Schwarcz: Reconfiguration of the union of arborescences, Proceedingsof the 34th International Symposium on Algorithms and Computation (ISAAC 2023), 44:1–44:14, 2023.
63. Yusuke Kobayashi and Tatsuya Terao: Subquadratic submodular maximization with a general matroid
constraint, Proceedings of the 51st EATCS International Colloquium on Automata, Languages andProgramming (ICALP 2024), to appear.

Last updated: May 15, 2024