Basic Information

Affiliated programs (koza)

• Graduate School of Science, 数学・数理解析専攻 応用数理講座, 准教授

Academic Degree

• 修士（情報理工学）(東京大学)
• 博士（情報理工学）(東京大学)

Research History

• Kyoto University Research Institute for Mathematical Sciences, Associate Professor

ID,URL

• ORCID ID

  0000-0001-9478-7307

• J-Global ID

  201701001400401915

• Researcher number

  40581591

• External link

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

Website(s) (URL(s))

• http://www.kurims.kyoto-u.ac.jp/~yusuke/index.html

researchmap URL

• https://researchmap.jp/yusuke_kobayashi

Research

Research Areas

• Informatics, Mathematical informatics

Papers

• Reforming an Envy-Free Matching

  Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki

  Algorithmica, 27 Jan. 2025

  
• Feedback vertex set reconfiguration in planar graphs

  Nicolas Bousquet; Felix Hommelsheim; Yusuke Kobayashi; Moritz Mühlenthaler; Akira Suzuki

  Theoretical Computer Science, Nov. 2023

  Access this paper :

  
• Envy-free relaxations for goods, chores, and mixed items

  Kristóf Bérczi; Erika R. Bérczi-Kovács; Endre Boros; Fekadu Tolessa Gedefa; Naoyuki Kamiyama; Telikepalli Kavitha; Yusuke Kobayashi; Kazuhisa Makino

  Theoretical Computer Science, Jun. 2024, Peer-reviewed

  
• Reconfiguration of Spanning Trees with Degree Constraints or Diameter Constraints.

  Nicolas Bousquet; Takehiro Ito; Yusuke Kobayashi 0001; Haruka Mizuta; Paul Ouvrard; Akira Suzuki; Kunihiro Wasa

  Algorithmica, Sep. 2023, Peer-reviewed

  
• On reachable assignments under dichotomous preferences

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki

  Theoretical Computer Science, Nov. 2023, Peer-reviewed

  
• Algorithmic Theory of Qubit Routing.

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto

  WADS, 2023, Peer-reviewed

  
• Optimal General Factor Problem and Jump System Intersection.

  Yusuke Kobayashi 0001

  Integer Programming and Combinatorial Optimization - 24th International Conference(IPCO), 2023, Peer-reviewed

  Access this paper :

  
• Reconfiguration of Time-Respecting Arborescences.

  Takehiro Ito; Yuni Iwamasa; Naoyuki Kamiyama; Yasuaki Kobayashi; Yusuke Kobayashi 0001; Shun-ichi Maezawa; Akira Suzuki

  WADS, 2023, Peer-reviewed

  
• A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems.

  Tesshu Hanaka; Masashi Kiyomi; Yasuaki Kobayashi; Yusuke Kobayashi 0001; Kazuhiro Kurita; Yota Otachi

  AAAI, 2023, Peer-reviewed

  
• Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra.

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto

  ICALP, 2023, Peer-reviewed

  
• Rerouting Planar Curves and Disjoint Paths.

  Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Yusuke Kobayashi 0001; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki

  ICALP, 2023, Peer-reviewed

  
• Fixed-parameter algorithms for graph constraint logic.

  Tatsuhiko Hatanaka; Felix Hommelsheim; Takehiro Ito; Yusuke Kobayashi 0001; Moritz Mühlenthaler; Akira Suzuki

  Theor. Comput. Sci., May 2023, Peer-reviewed

  
• Reconfiguration of Colorings in Triangulations of the Sphere.

  Takehiro Ito; Yuni Iwamasa; Yusuke Kobayashi 0001; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki

  SoCG, 2023, Peer-reviewed

  
• Trade-offs among degree, diameter, and number of paths.

  Toshimasa Ishii; Akitoshi Kawamura; Yusuke Kobayashi; Kazuhisa Makino

  Discret. Appl. Math., 2023, Peer-reviewed

  
• On Reachable Assignments Under Dichotomous Preferences

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki

  PRIMA 2022: Principles and Practice of Multi-Agent Systems, 2023, Peer-reviewed

  
• Reforming an Envy-Free Matching

  Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki

  Proceedings of the AAAI Conference on Artificial Intelligence, 28 Jun. 2022, Peer-reviewed

  
• Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles

  Yusuke Kobayashi

  Mathematical Programming, Mar. 2022, Peer-reviewed

  Access this paper :

  
• Parameterized Complexity of (A, ℓ )-Path Packing.

  Rémy Belmonte; Tesshu Hanaka; Masaaki Kanzaki; Masashi Kiyomi; Yasuaki Kobayashi; Yusuke Kobayashi; Michael Lampis; Hirotaka Ono; Yota Otachi

  Algorithmica, 2022, Peer-reviewed

  
• Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint.

  Nicolas Bousquet; Takehiro Ito; Yusuke Kobayashi; Haruka Mizuta; Paul Ouvrard; Akira Suzuki; Kunihiro Wasa

  STACS, 2022, Peer-reviewed

  
• Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams.

  Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki

  SODA, 2022, Peer-reviewed

  
• Shortest Reconfiguration of Perfect Matchings via Alternating Cycles

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  SIAM Journal on Discrete Mathematics, Jun. 2022, Peer-reviewed

  Access this paper :

  
• A Parameterized View to the Robust Recoverable Base Problem of Matroids Under Structural Uncertainty

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  Operations Research Letters, May 2022, Peer-reviewed

  Access this paper :

  
• Linear-Time Recognition of Double-Threshold Graphs

  Yusuke Kobayashi; Yoshio Okamoto; Yota Otachi; Yushi Uno

  Algorithmica, Apr. 2022, Peer-reviewed

  Access this paper :

  
• Market Pricing for Matroid Rank Valuations.

  Kristóf Bérczi; Naonori Kakimura; Yusuke Kobayashi

  SIAM Journal on Discrete Mathematics, 2021, Peer-reviewed

  Access this paper :

  
• A Weighted Linear Matroid Parity Algorithm

  Satoru Iwata; Yusuke Kobayashi

  SIAM Journal on Computing, 07 Jan. 2021, Peer-reviewed

  
• Algorithms for gerrymandering over graphs

  Takehiro Ito; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  Theoretical Computer Science, May 2021, Peer-reviewed

  Access this paper :

  
• Computing the Largest Bond and the Maximum Connected Cut of a Graph

  Gabriel L. Duarte; Hiroshi Eto; Tesshu Hanaka; Yasuaki Kobayashi; Yusuke Kobayashi; Daniel Lokshtanov; Lehilton L. C. Pedrosa; Rafael C. S. Schouery; Uéverton S. Souza

  Algorithmica, May 2021, Peer-reviewed

  
• Finding a maximum minimal separator: Graph classes and fixed-parameter tractability

  Tesshu Hanaka; Yasuaki Kobayashi; Yusuke Kobayashi; Tsuyoshi Yagita

  Theoretical Computer Science, Apr. 2021, Peer-reviewed

  
• Tight Approximation for Unconstrained XOS Maximization

  Yuval Filmus; Yasushi Kawase; Yusuke Kobayashi; Yutaro Yamaguchi

  Mathematics of Operations Research, 29 Mar. 2021, Peer-reviewed

  
• Submodular reassignment problem for reallocating agents to tasks with synergy effects

  Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  Discrete Optimization, Feb. 2021, Peer-reviewed

  
• Subgraph Isomorphism on Graph Classes that Exclude a Substructure

  Hans L. Bodlaender; Tesshu Hanaka; Yasuaki Kobayashi; Yusuke Kobayashi; Yoshio Okamoto; Yota Otachi; Tom C. van der Zanden

  Algorithmica, Dec. 2020, Peer-reviewed

  
• Diameter of colorings under Kempe changes

  Marthe Bonamy; Marc Heinrich; Takehiro Ito; Yusuke Kobayashi; Haruka Mizuta; Moritz Mühlenthaler; Akira Suzuki; Kunihiro Wasa

  Theoretical Computer Science, Oct. 2020, Peer-reviewed

  
• On the number of edges in a graph with many two-hop disjoint paths

  Koki Takayama; Yusuke Kobayashi

  Discrete Applied Mathematics, Sep. 2020, Peer-reviewed

  
• Linear-Time Recognition of Double-Threshold Graphs

  Yusuke Kobayashi; Yoshio Okamoto; Yota Otachi; Yushi Uno

  Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020), 2020, Peer-reviewed

  
• Fixed-Parameter Algorithms for Graph Constraint Logic

  Tatsuhiko Hatanaka; Felix Hommelsheim; Takehiro Ito; Yusuke Kobayashi; Moritz Mühlenthaler; Akira Suzuki

  Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), 2020, Peer-reviewed

  
• Market Pricing for Matroid Rank Valuations

  Kristóf Bérczi; Naonori Kakimura; Yusuke Kobayashi

  Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), 2020, Peer-reviewed

  
• Reconfiguration of Spanning Trees with Many or Few Leaves

  Nicolas Bousquet; Takehiro Ito; Yusuke Kobayashi; Haruka Mizuta; Paul Ouvrard; Akira Suzuki; Kunihiro Wasa

  Proceedings of the 28th European Symposium on Algorithms (ESA 2020), 2020, Peer-reviewed

  
• The Steiner Problem for Count Matroids

  Tibor Jordán; Yusuke Kobayashi; Ryoga Mahara; Kazuhisa Makino

  Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), 2020, Peer-reviewed

  
• Parameterized Complexity of (A, ℓ )-Path Packing

  Rémy Belmonte; Tesshu Hanaka; Masaaki Kanzaki; Masashi Kiyomi; Yasuaki Kobayashi; Yusuke Kobayashi; Michael Lampis; Hirotaka Ono; Yota Otachi

  Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), 2020, Peer-reviewed

  
• An FPT Algorithm for Minimum Additive Spanner Problem.

  Yusuke Kobayashi

  Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, Peer-reviewed

  
• Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles.

  Yusuke Kobayashi

  Proceedings of the 21st Conference on Integer Programming and Combinatorial Optimization (IPCO 2020), 2020, Peer-reviewed

  Access this paper :

  
• A strongly polynomial time algorithm for the maximum supply rate problem on trees.

  Koki Takayama; Yusuke Kobayashi

  Theor. Comput. Sci., 2020, Peer-reviewed

  
• Linear min-max relation between the treewidth of an H-minor-free graph and its largest grid minor.

  Ken-ichi Kawarabayashi; Yusuke Kobayashi

  J. Comb. Theory, Ser. B, 2020, Peer-reviewed

  
• Finding a path with two labels forbidden in group-labeled graphs.

  Yasushi Kawase; Yusuke Kobayashi; Yutaro Yamaguchi

  J. Comb. Theory, Ser. B, 2020, Peer-reviewed

  
• Shortest Reconfiguration of Colorings Under Kempe Changes.

  Marthe Bonamy; Marc Heinrich; Takehiro Ito; Yusuke Kobayashi; Haruka Mizuta; Moritz Mühlenthaler; Akira Suzuki; Kunihiro Wasa

  Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, Peer-reviewed

  
• Complexity of the multi-service center problem.

  Takehiro Ito; Naonori Kakimura; Yusuke Kobayashi 0001

  Theor. Comput. Sci., 2020, Peer-reviewed

  
• Improved Analysis of Highest-Degree Branching for Feedback Vertex Set.

  Yoichi Iwata; Yusuke Kobayashi

  Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), 2019, Peer-reviewed

  
• Parameterized Algorithms for Maximum Cut with Connectivity Constraints.

  Hiroshi Eto; Tesshu Hanaka; Yasuaki Kobayashi; Yusuke Kobayashi

  Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), 2019, Peer-reviewed

  
• Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  Proceedings of the 27th European Symposium on Algorithms (ESA 2019), 2019, Peer-reviewed

  
• The Perfect Matching Reconfiguration Problem.

  Marthe Bonamy; Nicolas Bousquet; Marc Heinrich; Takehiro Ito; Yusuke Kobayashi 0001; Arnaud Mary; Moritz Mühlenthaler; Kunihiro Wasa

  Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), 2019, Peer-reviewed

  
• An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number.

  Yasuaki Kobayashi; Yusuke Kobayashi; Shuichi Miyazaki; Suguru Tamaki

  Proceedings of the 30th International Workshop on Combinatorial Algorithms (IWOCA 2019), 2019, Peer-reviewed

  
• Diameter of Colorings Under Kempe Changes.

  Marthe Bonamy; Marc Heinrich; Takehiro Ito; Yusuke Kobayashi 0001; Haruka Mizuta; Moritz Mühlenthaler; Akira Suzuki; Kunihiro Wasa

  Proceedings of the 25th Annual International Computing and Combinatorics Conference (COCOON 2019), 2019, Peer-reviewed

  
• Algorithms for Gerrymandering over Graphs.

  Takehiro Ito; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto

  Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), 2019, Peer-reviewed

  
• Reconfiguration of maximum-weight b-matchings in a graph.

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  J. Comb. Optim., 2019, Peer-reviewed

  
• Two disjoint shortest paths problem with non-negative edge length.

  Yusuke Kobayashi 0001; Ryo Sako

  Oper. Res. Lett., 2019, Peer-reviewed

  Access this paper :

  
• Minimum-Cost b-Edge Dominating Sets on Trees.

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  Algorithmica, 2019, Peer-reviewed

  
• Optimal cache placement for an academic backbone network

  Than Nguyen Hau; Naonori Kakimura; Ken-Ichi Kawarabayashi; Yusuke Kobayashi; Tatsuya Matsuoka; Yu Yokoi

  Journal of the Operations Research Society of Japan, 01 Apr. 2018, Peer-reviewed

  
• The parity Hamiltonian cycle problem

  Hiroshi Nishiyama; Yusuke Kobayashi; Yukiko Yamauchi; Shuji Kijima; Masafumi Yamashita

  Discrete Mathematics, 2018, Peer-reviewed

  
• Tight Approximability of the Server Allocation Problem for Real-Time Applications

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto; Taichi Shiitada

  Algorithmic Aspects of Cloud Computing, 2018, Peer-reviewed

  
• A Strongly Polynomial Time Algorithm for the Maximum Supply Rate Problem on Trees.

  Koki Takayama; Yusuke Kobayashi

  Proceedings of the 12th International Frontiers of Algorithmics Workshop (FAW 2018), 2018, Peer-reviewed

  
• NP-hardness and fixed-parameter tractability of the minimum spanner problem

  Yusuke Kobayashi

  Theoretical Computer Science, 2018, Peer-reviewed

  Access this paper :

  
• All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs

  Ken-ichi Kawarabayashi; Yusuke Kobayashi

  SIAM Journal on Computing, 2018, Peer-reviewed

  
• Randomized strategies for cardinality robustness in the knapsack problem

  Yusuke Kobayashi; Kenjiro Takazawa

  Theoretical Computer Science, 07 Nov. 2017, Peer-reviewed

  
• An algorithm for identifying cycle-plus-triangles graphs

  Kristóf Bérczi; Yusuke Kobayashi

  Discrete Applied Mathematics, 31 Jul. 2017, Peer-reviewed

  
• A weighted linear matroid parity algorithm

  Satoru Iwata; Yusuke Kobayashi

  Proceedings of the Annual ACM Symposium on Theory of Computing, 19 Jun. 2017, Peer-reviewed

  
• On Applications of Weighted Linear Matroid Parity

  Yusuke Kobayashi; Yutaro Yamaguchi

  The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, May 2017

  
• Efficient stabilization of cooperative matching games

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  Theoretical Computer Science, May 2017, Peer-reviewed

  
• Finding a shortest non-zero path in group-labeled graphs via permanent computation

  Yusuke Kobayashi; Sho Toyooka

  Algorithmica, 2017, Peer-reviewed

  
• Packing edge-disjoint odd Eulerian subgraphs through prescribed vertices in 4-edge-connected graphs

  Naonori Kakimura; Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  SIAM Journal on Discrete Mathematics, 2017, Peer-reviewed

  
• Reconfiguration of maximum-weight b-matchings in a graph

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017), 2017, Peer-reviewed

  
• The directed disjoint shortest paths problem

  Kristóf Bérczi; Yusuke Kobayashi

  Proceedings of the 25th European Symposium on Algorithms (ESA 2017), 2017, Peer-reviewed

  
• An improved approximation algorithm for the edge-disjoint paths problem with congestion two

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  ACM Transactions on Algorithms, 01 Sep. 2016, Peer-reviewed

  
• Edge-disjoint odd cycles in 4-edge-connected graphs

  Ken-ichi Kawarabayashi; Yusuke Kobayashi

  Journal of Combinatorial Theory. Series B, 01 Jul. 2016, Peer-reviewed

  
• Improved max-flow min-cut algorithms in a Circular Disk Failure Model with application to a road network

  Kensuke Otsuki; Yusuke Kobayashi; Kazuo Murota

  European Journal of Operational Research, 16 Jan. 2016, Peer-reviewed

  
• Covering intersecting bi-set families under matroid constraints

  Kristóf Bérczi; Tamás Király; Yusuke Kobayashi

  SIAM Journal on Discrete Mathematics, 2016, Peer-reviewed

  
• Randomized strategies for cardinality robustness in the knapsack problem

  Yusuke Kobayashi; Kenjiro Takazawa

  Proceedings of the 13th Meeting on Analytic Algorithmics and Combinatorics (ANALCO 2016), 2016, Peer-reviewed

  
• Efficient stabilization of cooperative matching games

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), 2016, Peer-reviewed

  
• The complexity of minimizing the difference of two M-convex set functions

  Yusuke Kobayashi

  Operations Research Letters, 01 Nov. 2015, Peer-reviewed

  
• Selecting vertex disjoint paths in plane graphs

  Holger Flier; Matúš Mihalák; Peter Widmayer; Anna Zych; Yusuke Kobayashi; Anita Schöbel

  Networks, 01 Sep. 2015, Peer-reviewed

  
• The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  Combinatorica, 22 Aug. 2015, Peer-reviewed

  
• Routing algorithms under mutual interference constraints

  Kota Ishihara; Yusuke Kobayashi

  Journal of the Operations Research Society of Japan, 01 Jul. 2015, Peer-reviewed

  
• Fence patrolling by mobile agents with distinct speeds

  Akitoshi Kawamura; Yusuke Kobayashi

  Distributed Computing, 01 Jan. 2015, Peer-reviewed

  
• The generalized terminal backup problem

  Attila Bernáth; Yusuke Kobayashi; Tatsuya Matsuoka

  SIAM Journal on Discrete Mathematics, 2015, Peer-reviewed

  
• Finding a path in group-labeled graphs with two labels forbidden

  Yasushi Kawase; Yusuke Kobayashi; Yutaro Yamaguchi

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2015, Peer-reviewed

  
• Triangle-free 2-matchings and M-concave functions on jump systems

  Yusuke Kobayashi

  Discrete Applied Mathematics, 01 Oct. 2014, Peer-reviewed

  
• The generalized terminal backup problem

  Attila Bernáth; Yusuke Kobayashi

  Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 2014, Peer-reviewed

  
• Max-flow min-cut theorem and faster algorithms in a circular disk failure model

  Yusuke Kobayashi; Kensuke Otsuki

  Proceedings - IEEE INFOCOM, 2014, Peer-reviewed

  
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi; Stephan Kreutzer

  Proceedings of the Annual ACM Symposium on Theory of Computing, 2014, Peer-reviewed

  
• Minimum-cost b-Edge dominating sets on trees

  Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, Peer-reviewed

  
• An O(log n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  ACM Transactions on Algorithms, 2013, Peer-reviewed

  
• Robust matchings and matroid intersections

  Ryo Fujita; Yusuke Kobayashi; Kazuhisa Makino

  SIAM Journal on Discrete Mathematics, 2013, Peer-reviewed

  
• All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2013, Peer-reviewed

  
• Cone superadditivity of discrete convex functions

  Yusuke Kobayashi; Kazuo Murota; Robert Weismantel

  Mathematical Programming, Oct. 2012, Peer-reviewed

  
• A proof of Cunningham's conjecture on restricted subgraphs and jump systems

  Yusuke Kobayashi; Jácint Szabó; Kenjiro Takazawa

  Journal of Combinatorial Theory. Series B, Jul. 2012, Peer-reviewed

  
• Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem

  Ken-ichi Kawarabayashi; Yusuke Kobayashi

  Journal of Combinatorial Theory. Series B, Jul. 2012, Peer-reviewed

  
• Testing the (s, t) -disconnectivity of graphs and digraphs

  Yuichi Yoshida; Yusuke Kobayashi

  Theoretical Computer Science, 25 May 2012, Peer-reviewed

  
• An algorithm for (n-3)-connectivity augmentation problem: Jump system approach

  Kristóf Bérczi; Yusuke Kobayashi

  Journal of Combinatorial Theory. Series B, May 2012, Peer-reviewed

  
• An algorithm for finding a maximum t-matching excluding complete partite subgraphs

  Yusuke Kobayashi; Xin Yin

  Discrete Optimization, May 2012, Peer-reviewed

  
• The disjoint paths problem in quadratic time

  Ken-ichi Kawarabayashi; Yusuke Kobayashi; Bruce Reed

  Journal of Combinatorial Theory. Series B, Mar. 2012, Peer-reviewed

  
• A linear time algorithm for the induced disjoint paths problem in planar graphs

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  Journal of Computer and System Sciences, Mar. 2012, Peer-reviewed

  
• An immersion of a square in 4-edge-connected graphs

  Ken-ichi Kawarabayashi; Yusuke Kobayashi

  Progress in Informatics, Mar. 2012, Peer-reviewed

  
• The complexity of the node capacitated in-tree packing problem

  Shinji Imahori; Yuichiro Miyamoto; Hideki Hashimoto; Yusuke Kobayashi; Mihiro Sasaki; Mutsunori Yagiura

  Networks, Jan. 2012, Peer-reviewed

  
• Algorithms for finding a maximum non-k-linked graph

  Yusuke Kobayashi; Yuichi Yoshida

  SIAM Journal on Discrete Mathematics, 2012, Peer-reviewed

  
• Erd\H{o}s-P\'osa property and its algorithmic applications --- parity constraints, subset feedback set, and subset packing

  Naonori Kakimura; Ken-ichi Kawarabayashi; Yusuke Kobayashi

  Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 2012, Peer-reviewed

  
• List-coloring graphs without subdivisions and without immersions

  Ken-ichi Kawarabayashi; Yusuke Kobayashi

  Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 2012, Peer-reviewed

  
• Edge-disjoint odd cycles in 4-edge-connected Graphs

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  Leibniz International Proceedings in Informatics, LIPIcs, 2012, Peer-reviewed

  
• Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid minor

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  Leibniz International Proceedings in Informatics, LIPIcs, 2012, Peer-reviewed

  
• Fence patrolling by mobile agents with distinct speeds

  Akitoshi Kawamura; Yusuke Kobayashi

  Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), 2012, Peer-reviewed

  
• An improved algorithm for the half-disjoint paths problem

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  SIAM Journal on Discrete Mathematics, 2011, Peer-reviewed

  
• Breaking O(n1/2)-approximation algorithms for the edge-disjoint paths problem with congestion two

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  Proceedings of the Annual ACM Symposium on Theory of Computing, 2011, Peer-reviewed

  
• Algorithms for finding a maximum non-kappa;-linked graph

  Yusuke Kobayashi; Yuichi Yoshida

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2011, Peer-reviewed

  
• A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs

  Yusuke Kobayashi

  Discrete Optimization, Nov. 2010, Peer-reviewed

  
• On shortest disjoint paths in planar graphs

  Yusuke Kobayashi; Christian Sommer

  Discrete Optimization, Nov. 2010, Peer-reviewed

  
• Algorithms for finding an induced cycle in planar graphs

  Ken-ichi Kawarabayashi; Yusuke Kobayashi

  Combinatorica, Nov. 2010, Peer-reviewed

  
• An algorithm for minimum cost arc-connectivity orientations

  Satoru Iwata; Yusuke Kobayashi

  Algorithmica (New York), Apr. 2010, Peer-reviewed

  
• The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs

  Ken-ichi Kawarabayashi; Yusuke Kobayashi

  PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2010, Peer-reviewed

  
• An O(log n)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Gr

  Ken-ichi Kawarabayashi; Yusuke Kobayashi

  APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 2010, Peer-reviewed

  
• Improved Algorithm for the Half-Disjoint Paths Problem

  Ken-ichi Kawarabayashi; Yusuke Kobayashi

  APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 2010, Peer-reviewed

  
• Robust Matchings and Matroid Intersections

  Ryo Fujita; Yusuke Kobayashi; Kazuhisa Makino

  ALGORITHMS-ESA 2010, PT II, 2010, Peer-reviewed

  
• Induced disjoint paths problem in a planar digraph

  Yusuke Kobayashi

  Discrete Applied Mathematics, 06 Aug. 2009, Peer-reviewed

  
• Even factors, jump systems, and discrete convexity

  Yusuke Kobayashi; Kenjiro Takazawa

  Journal of Combinatorial Theory. Series B, Jan. 2009, Peer-reviewed

  
• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs

  Yusuke Kobayashi; Ken-ichi Kawarabayashi

  Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), 2009, Peer-reviewed

  
• The complexity of the node capacitated in-tree packing problem

  Shinji Imahori; Yuichiro Miyamoto; Hideki Hashimoto; Yusuke Kobayashi; Mihiro Sasaki; Mutsunori Yagiura

  Proceedings of the International Network Optimization Conference 2009, 2009, Peer-reviewed

  
• On shortest disjoint paths in planar graphs

  Yusuke Kobayashi; Christian Sommer

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2009, Peer-reviewed

  
• The induced disjoint paths problem

  Ken-Ichi Kawarabayashi; Yusuke Kobayashi

  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2008, Peer-reviewed

  
• Induction of M-convex functions by linking systems

  Yusuke Kobayashi; Kazuo Murota

  Discrete Applied Mathematics, 01 Jun. 2007, Peer-reviewed

  
• Operations on M-convex functions on jump systems

  Yusuke Kobayashi; Kazuo Murota; Ken'ichiro Tanaka

  SIAM Journal on Discrete Mathematics, 2007, Peer-reviewed

  

Awards

• 14 Sep. 2023

  （公社）日本オペレーションズ・リサーチ学会, 研究賞

  小林佑輔
• 04 Feb. 2011

  （公財）井上科学振興財団, 井上研究奨励賞
• 04 Feb. 2012

  （公財）船井情報科学振興財団, FFIT研究奨励賞
• 12 Sep. 2012

  （公社）日本オペレーションズ・リサーチ学会, 研究奨励賞
• 21 Jun. 2017

  ACM SIGACT, STOC 2017 Best Paper Award
• 25 Jul. 2019

  IWOCA 2019 Best Paper Award
• 14 Apr. 2020

  科学技術分野の文部科学大臣表彰 若手科学者賞
• 17 Oct. 2020

  藤原洋数理科学賞奨励賞
• 26 Aug. 2021

  船井情報科学振興財団, FIT船井ベストペーパー賞

External funds: Kakenhi

• Road infrastructure maintenance management by vehicle miles traveled tax -Entering the digital era of EVs and vehicle authentication-

  Grant-in-Aid for Challenging Research (Pioneering)

  Medium-sized Section 7:Economics, business administration, and related fields

  University of Tsukuba

  Yoshiaki Ohsawa

  From 28 Jun. 2019, To 31 Mar. 2023, Project Closed

  インフラ維持管理;モビリティ;電気自動車;予約システム;受益者負担;MaaS;交通課金;費用便益分析;均衡;シェアリング;課金;EV;ネットワーク流;オフグリッド;ドローン;電動自動車;移動革命;グラフ理論;交通ネットワーク

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K20417/
• 組合せ最適化における多面体手法の高度化

  Grant-in-Aid for Scientific Research (C)

  Basic Section 60020:Mathematical informatics-related

  Kyoto University

  小林 佑輔

  From 01 Apr. 2020, To 31 Mar. 2025, Granted

  組合せ最適化;アルゴリズム;多項式時間

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K11692/
• Development of Combinatorial Reconfiguration by Mathematics Approach: From Examples to New Methods

  Grant-in-Aid for Transformative Research Areas (B)

  Transformative Research Areas, Section (IV)

  The University of Electro-Communications

  Yoshio OKAMOTO

  From 02 Oct. 2020, To 31 Mar. 2023, Project Closed

  組合せ遷移;数学;離散数学;アルゴリズム;計算複雑性

  https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05795/
• Large Graphs: Theory and Algorithms

  Grant-in-Aid for Scientific Research (S)

  Broad Section J

  National Institute of Informatics

  河原林 健一

  From 11 Jun. 2018, To 31 Mar. 2023, Granted

  グラフアルゴリズム;グラフ理論;グラフ;離散数学;アルゴリズム;離散最適化;組合せ最適化;分散計算;サブモジュラー関数;計算理論

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18H05291/
• Analysis of unbounded scheduling problems

  Grant-in-Aid for Challenging Research (Exploratory)

  Kyoto University;Kyushu University

  Akitoshi Kawamura

  From 30 Jun. 2017, To 31 Mar. 2023, Project Closed

  スケジューリング;遷移可能性;ヘドニックゲーム;仕事割当;警邏問題;ナッシュ均衡;詰込問題;最適化;周期性;資源配置;マルチエージェント;無羨望性;提携構造形成;近似率;被覆問題;グラフ探索;計算幾何;貪慾法;算法設計

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17K19960/
• Study on Theory of Combinatorial Optimization with Applications to Robust Network Design

  Grant-in-Aid for Young Scientists (B)

  Kyoto University;University of Tsukuba

  Yusuke Kobayashi

  From 01 Apr. 2016, To 31 Mar. 2020, Project Closed

  組合せ最適化;アルゴリズム;グラフ;グラフアルゴリズム

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16K16010/
• Optimization problems with time and it's applications on networks.

  Grant-in-Aid for Scientific Research (B)

  University of Tsukuba

  Maiko SHIGENO

  From 01 Apr. 2016, To 31 Mar. 2020, Project Closed

  ネットワーク;アルゴリズム;最適化理論;数理工学;応用数学;データ分析;ネットワーク理論

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16H03118/
• Construction of basic theory to accelerate the utilization of conic optimization in the real world

  Grant-in-Aid for Scientific Research (B)

  University of Tsukuba

  Akiko Yoshise

  From 01 Apr. 2015, To 31 Mar. 2019, Project Closed

  錐最適化;半正定値最適化;二重非負値最適化;共正値最適化;線形計画問題;二重非負値錐;共正値錐;線形計画法;勾配法;半正定値錐;半正定値計画問題;半正定値基

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15H02966/
• Theory and Experimental Study of Selecting, Consolidating, and Overhauling Aged Urban Infrastructures

  Grant-in-Aid for Scientific Research (A)

  University of Tsukuba

  Yoshiaki OHSAWA

  From 01 Apr. 2013, To 31 Mar. 2017, Project Closed

  老朽化;都市インフラ;地方分権;アセットマネジメント;フリーライダー;コンパクトシティ;人口減少;財政逼迫;公共施設;選択と集中;広域連携;自治体実装;スケジューリング

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-25242029/
• Using dual concepts in graph minor algorithms

  Grant-in-Aid for Young Scientists (B)

  University of Tsukuba;The University of Tokyo

  Yusuke KOBAYASHI

  From 01 Apr. 2012, To 31 Mar. 2017, Project Closed

  アルゴリズム;グラフ;組合せ最適化;辺素パス問題;グラフマイナー理論;グラフアルゴリズム

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-24700004/
• Exploring the limits of computation from mathematical logic

  Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)

  Science and Engineering

  Kyoto University

  Kazuhisa Makino

  From 28 Jun. 2012, To 31 Mar. 2017, Project Closed

  computation;計算量;反マトロイド;回路計算量;実数計算量;計算複雑度

  https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-24106002/
• Research on algorithms based on graph minor theory

  Grant-in-Aid for Research Activity Start-up

  The University of Tokyo

  Yusuke KOBAYASHI

  From 01 Apr. 2010, To 31 Mar. 2012, Project Closed

  グラフ;アルゴリズム;グラフ理論

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22800005/
• Unified Optimization Theory by Discrete Convex Paradigm

  Grant-in-Aid for Scientific Research (B)

  The University of Tokyo

  Kazuo MUROTA

  From 01 Apr. 2009, To 31 Mar. 2015, Project Closed

  離散最適化;凸関数;双対性;劣モジュラ関数;マトロイド;数理工学;最適化;アルゴリズム

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21360045/
• Graph Algorithms and Optimization: Theory and Scalable Algorithms

  Grant-in-Aid for Scientific Research (S)

  Broad Section J

  National Institute of Informatics

  河原林 健一

  From 27 Apr. 2022, To 31 Mar. 2027, Granted

  離散数学;グラフアルゴリズム;グラフ;アルゴリズム;グラフ構造;グラフ理論;組合せ最適化

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22H05001/
• 多面体的手法と離散構造を用いた組合せ最適化問題の解法

  Grant-in-Aid for Scientific Research (B)

  Basic Section 60010:Theory of informatics-related

  Kyoto University

  小林 佑輔

  From 01 Apr. 2024, To 31 Mar. 2029, Granted

  組合せ最適化;アルゴリズム

  https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-24K02901/

Education

Teaching subject(s)

• From 01 Apr. 2025, To 31 Mar. 2026

  Seminar on Algorithm Theory b

  1336, Fall, Graduate School of Science, 3
• From 01 Apr. 2025, To 31 Mar. 2026

  Seminar on Algorithm Theory a

  1335, Spring, Graduate School of Science, 3
• From 01 Apr. 2025, To 31 Mar. 2026

  Seminar on Algorithm Theory d

  1338, Fall, Graduate School of Science, 3
• From 01 Apr. 2025, To 31 Mar. 2026

  Seminar on Algorithm Theory c

  1337, Spring, Graduate School of Science, 3
• From 01 Apr. 2024, To 31 Mar. 2025

  Special study course (Mathematical Science)

  5140, Year-long, Faculty of Science, 12
• From 01 Apr. 2024, To 31 Mar. 2025

  Seminar on Algorithm Theory d

  1338, Fall, Graduate School of Science, 3
• From 01 Apr. 2024, To 31 Mar. 2025

  Seminar on Algorithm Theory c

  1337, Spring, Graduate School of Science, 3
• From 01 Apr. 2024, To 31 Mar. 2025

  Seminar on Algorithm Theory b

  1336, Fall, Graduate School of Science, 3
• From 01 Apr. 2024, To 31 Mar. 2025

  Seminar on Algorithm Theory a

  1335, Spring, Graduate School of Science, 3
• From 01 Apr. 2023, To 31 Mar. 2024

  Special study course (Mathematical Science)

  5140, Year-long, Faculty of Science, 12
• From 01 Apr. 2023, To 31 Mar. 2024

  Seminar on Algorithm Theory a

  1335, Spring, Graduate School of Science, 3
• From 01 Apr. 2023, To 31 Mar. 2024

  Seminar on Algorithm Theory d

  1338, Fall, Graduate School of Science, 3
• From 01 Apr. 2023, To 31 Mar. 2024

  Seminar on Algorithm Theory c

  1337, Spring, Graduate School of Science, 3
• From 01 Apr. 2023, To 31 Mar. 2024

  Seminar on Algorithm Theory b

  1336, Fall, Graduate School of Science, 3
• From 01 Apr. 2022, To 31 Mar. 2023

  Special study course (Mathematical Science)

  5140, Year-long, Faculty of Science, 12
• From 01 Apr. 2022, To 31 Mar. 2023

  Seminar on Algorithm Theory a

  1335, Spring, Graduate School of Science, 3
• From 01 Apr. 2022, To 31 Mar. 2023

  Seminar on Algorithm Theory c

  1337, Spring, Graduate School of Science, 3
• From 01 Apr. 2022, To 31 Mar. 2023

  Seminar on Algorithm Theory b

  1336, Fall, Graduate School of Science, 3
• From 01 Apr. 2022, To 31 Mar. 2023

  Seminar on Algorithm Theory d

  1338, Fall, Graduate School of Science, 3
• From Apr. 2019, To Mar. 2020

  Mathematics seminary

  Year-long, 理学部
• From Apr. 2019, To Mar. 2020

  Seminar on Algorithm Theory a

  Spring, 理学研究科
• From Apr. 2019, To Mar. 2020

  Seminar on Algorithm Theory b

  Fall, 理学研究科
• From Apr. 2019, To Mar. 2020

  Seminar on Algorithm Theory c

  Spring, 理学研究科
• From Apr. 2019, To Mar. 2020

  Seminar on Algorithm Theory d

  Fall, 理学研究科
• From Apr. 2020, To Mar. 2021

  Special study course (Mathematical Science)

  Year-long, 理学部
• From Apr. 2020, To Mar. 2021

  Seminar on Algorithm Theory a

  Spring, 理学研究科
• From Apr. 2020, To Mar. 2021

  Seminar on Algorithm Theory b

  Fall, 理学研究科
• From Apr. 2020, To Mar. 2021

  Seminar on Algorithm Theory c

  Spring, 理学研究科
• From Apr. 2020, To Mar. 2021

  Seminar on Algorithm Theory d

  Fall, 理学研究科
• From Apr. 2021, To Mar. 2022

  Special study course (Mathematical Science)

  Year-long, 理学部
• From Apr. 2021, To Mar. 2022

  Seminar on Algorithm Theory a

  Spring, 理学研究科
• From Apr. 2021, To Mar. 2022

  Seminar on Algorithm Theory b

  Fall, 理学研究科
• From Apr. 2021, To Mar. 2022

  Seminar on Algorithm Theory c

  Spring, 理学研究科
• From Apr. 2021, To Mar. 2022

  Seminar on Algorithm Theory d

  Fall, 理学研究科

Participation in PhD Defense

• Extension of Additive Valuations to General Valuations on the Existence of EFX

  MAHARA RYOGA, Graduate School of Science, Chief Examiner

  23 Mar. 2023