Yusuke Kobayashi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Yusuke Kobayashi has a total of 79 co-authors. Here are the top co-authors by number of shared publications:
- Yoshio Okamoto
Graduate School of Informatics and Engineering, The University of Electro-Communications, Chofu, Japan
15 shared publications - Naoyuki Kamiyama
Institute of Mathematics for Industry, Kyushu University, Fukuoka, Japan
13 shared publications - Naonori Kakimura
Faculty of Science and Technology, Keio University, Yokohama, Japan
12 shared publications - Takehiro Ito
Graduate School of Information Sciences, Tohoku University, Sendai, Japan
12 shared publications - Yasuaki Kobayashi
Hokkaido University
9 shared publications - Yota Otachi
Nagoya University
8 shared publications
Latest Publications
- Open Access
- 18 June 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1083
Loss minimization for electrical flows over spanning trees on grids
- 18 June 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1083
Open AccessLoss minimization for electrical flows over spanning trees on grids
- 13 June 2026
- Published by Springer Nature
- p. 17-31
A PTAS for Weighted Triangle-Free 2-Matching
- 13 June 2026
- Published by Springer Nature
- p. 362-377
Polynomial Kernels with Reachability for Weighted d-Matroid Intersection
- 13 June 2026
- Published by Springer Nature
- p. 362-377
Polynomial Kernels with Reachability for Weighted d-Matroid Intersection
- 29 May 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (2) , 816-835
Finding a Maximum Restricted \({t}\)-Matching via Boolean Edge-CSPThe problem of finding a maximum 2-matching without short cycles has received significant attention due to its relevance to the Hamiltonian cycle problem. This problem is generalized to finding a maximum [Formula: see text]-matching which excludes specified complete [Formula: see text]-partite subgraphs, where [Formula: see text] is a fixed positive integer. The polynomial solvability of this generalized problem remains an open question. In this paper, we present polynomial-time algorithms for the following two cases of this problem: in the first case the forbidden complete [Formula: see text]-partite subgraphs are edge-disjoint, and in the second case the maximum degree of the input graph is at most [Formula: see text]. Our result for the first case extends the previous work of Nam (1994), showing the polynomial solvability of the problem of finding a maximum 2-matching without cycles of length four, where the cycles of length four are vertex-disjoint. The second result expands upon the works of Bérczi and Végh (2010) and Kobayashi and Yin (2012), which focused on graphs with maximum degree at most [Formula: see text]. Our algorithms are obtained from exploiting the discrete structure of restricted [Formula: see text]-matchings and employing an algorithm for the Boolean edge-CSP.
- 29 May 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (2) , 816-835
Finding a Maximum Restricted \({t}\)-Matching via Boolean Edge-CSPThe problem of finding a maximum 2-matching without short cycles has received significant attention due to its relevance to the Hamiltonian cycle problem. This problem is generalized to finding a maximum [Formula: see text]-matching which excludes specified complete [Formula: see text]-partite subgraphs, where [Formula: see text] is a fixed positive integer. The polynomial solvability of this generalized problem remains an open question. In this paper, we present polynomial-time algorithms for the following two cases of this problem: in the first case the forbidden complete [Formula: see text]-partite subgraphs are edge-disjoint, and in the second case the maximum degree of the input graph is at most [Formula: see text]. Our result for the first case extends the previous work of Nam (1994), showing the polynomial solvability of the problem of finding a maximum 2-matching without cycles of length four, where the cycles of length four are vertex-disjoint. The second result expands upon the works of Bérczi and Végh (2010) and Kobayashi and Yin (2012), which focused on graphs with maximum degree at most [Formula: see text]. Our algorithms are obtained from exploiting the discrete structure of restricted [Formula: see text]-matchings and employing an algorithm for the Boolean edge-CSP.
- 23 April 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1077
Hardness and fixed parameter tractability for pinwheel scheduling problems
- 23 April 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1077
Hardness and fixed parameter tractability for pinwheel scheduling problems
- 8 April 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (2) , 554-575
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem ra...
- 8 April 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (2) , 554-575
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem ra...
- 22 December 2025
- Published by Springer Nature in Algorithmica
- Vol. 88 (1) , 15
Reconfiguration of Time-Respecting Arborescences
- 22 December 2025
- Published by Springer Nature in Algorithmica
- Vol. 88 (1) , 15
Reconfiguration of Time-Respecting Arborescences
- Open Access
- 31 October 2025
- Published by The Operations Research Society of Japan in Journal of the Operations Research Society of Japan
- Vol. 68 (4) , 133-150
AN ADDITIVE APPROXIMATION SCHEME FOR THE NASH SOCIAL WELFARE MAXIMIZATION WITH IDENTICAL ADDITIVE VALUATIONS
We study the problem of efficiently and fairly allocating a set of indivisible goods among agents with identical and additive valuations for the goods. The objective is to maximize the Nash social welfare, which is the geometric mean of the agents’ valuations. While maximizing the Nash social welfare is NP-hard, a PTAS for this problem is presented by Nguyen and Rothe. The main contribution of this paper is to design a first additive PTAS for this problem, that is, we give a polynomial-time algorithm that maximizes the Nash social welfare within an additive error ευmax, where ε is an arbitrary positive number and υmax is the maximum utility of goods. The approximation guarantee of our algorithm is better than that of a PTAS. The idea of our algorithm is simple; we apply a preprocessing and then utilize an additive PTAS for the target load balancing problem given recently by Buchem et al. However, a nontrivial amount of work is required to evaluate the additive error of the output.
- 31 October 2025
- Published by The Operations Research Society of Japan in Journal of the Operations Research Society of Japan
- Vol. 68 (4) , 133-150
Open AccessAN ADDITIVE APPROXIMATION SCHEME FOR THE NASH SOCIAL WELFARE MAXIMIZATION WITH IDENTICAL ADDITIVE VALUATIONS
We study the problem of efficiently and fairly allocating a set of indivisible goods among agents with identical and additive valuations for the goods. The objective is to maximize the Nash social welfare, which is the geometric mean of the agents’ valuations. While maximizing the Nash social welfare is NP-hard, a PTAS for this problem is presented by Nguyen and Rothe. The main contribution of this paper is to design a first additive PTAS for this problem, that is, we give a polynomial-time algorithm that maximizes the Nash social welfare within an additive error ευmax, where ε is an arbitrary positive number and υmax is the maximum utility of goods. The approximation guarantee of our algorithm is better than that of a PTAS. The idea of our algorithm is simple; we apply a preprocessing and then utilize an additive PTAS for the target load balancing problem given recently by Buchem et al. However, a nontrivial amount of work is required to evaluate the additive error of the output.
- Open Access
- 30 May 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 6 (3) , 1-17
Algorithmic Theory of Qubit Routing in the Linear Nearest Neighbor Architectures
The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We show that the qubit routing problem on a path can be solved in a fixed-parameter time where the number of two-qubit gates is a parameter. (3) We show that the qubit routing problem on a path can be solved in polynomial time if each qubit is involved in at most one two-qubit gate.
- 30 May 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 6 (3) , 1-17
Open AccessAlgorithmic Theory of Qubit Routing in the Linear Nearest Neighbor Architectures
The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We show that the qubit routing problem on a path can be solved in a fixed-parameter time where the number of two-qubit gates is a parameter. (3) We show that the qubit routing problem on a path can be solved in polynomial time if each qubit is involved in at most one two-qubit gate.