SEARCH

Search Details

Kobayashi Yasuaki

Faculty of Information Science and Technology　Computer Science and Information Technology　Knowledge Software ScienceAssociate Professor

Researcher basic information

■ Degree
  • 博士（理学）, 明治大学
■ URL
researchmap URLホームページURL■ Various IDs
Researcher number
  • 60735083
J-Global ID■ Research Keywords and Fields
Research Field
  • Informatics, Mathematical informatics
  • Informatics, Intelligent informatics
  • Informatics, Theory of informatics
■ Educational Organization

Research activity information

■ Awards
  • 2024, WALCOM 2024, Best Paper Award
  • 2021, 人工知能学会, 研究会優秀賞
  • 2019, IWOCA 2019 Best Paper Award
  • 2017, The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge, Track B, 1st place
  • 2014, 情報処理学会, コンピューターサイエンス領域奨励賞
  • 2012, 日本オペレーションズ・リサーチ学会 「OR横断若手の会研究部会」, 学生優秀発表賞
■ Papers
  • Independent Set Reconfiguration on Directed Graphs
    Takehiro Ito; Yuni Iwamasa; Yasuaki Kobayashi; Yu Nakahata; Yota Otachi; Masahiro Takahashi; Kunihiro Wasa
    SIAM Journal on Discrete Mathematics, 40, 1, 82, 101, 31 Mar. 2026, [Peer-reviewed]
    Scientific journal
  • Reconfiguration of Time-Respecting Arborescences.
    Takehiro Ito; Yuni Iwamasa; Naoyuki Kamiyama; Yasuaki Kobayashi; Yusuke Kobayashi; Shun-ichi Maezawa; Akira Suzuki
    Algorithmica, 88, 1, 15, 15, Feb. 2026, [Peer-reviewed]
    Scientific journal
  • SRIP: A SAT-based System for Independent Set Reconfiguration.
    Takehide Soh; Akifumi Kuwahara; Mutsunori Banbara; Naoyuki Tamura; Yasuaki Kobayashi; Yuta Nozaki; Takehiro Ito
    KR, 2026
    International conference proceedings
  • Finding One Local Optimum Is Easy - but What About Two?
    Yasuaki Kobayashi; Kazuhiro Kurita; Yutaro Yamaguchi
    AAAI 2026, 40, 43, 37009, 37017, 2026, [Peer-reviewed]
    English, International conference proceedings
  • Finding Order-Preserving Subgraphs
    Haruya Imamura; Yasuaki Kobayashi; Yota Otachi; Toshiki Saitoh; Keita Sato; Asahi Takaoka; Ryo Yoshinaka; Tom C. van der Zanden
    Proceedings of WALCOM 2026, Lecture Notes in Computer Science, 16444, 157, 171, 2026, [Peer-reviewed]
    International conference proceedings
  • Forcing a Unique Minimum Spanning Tree and a Unique Shortest Path
    Tatsuya Gima; Yasuaki Kobayashi; Yota Otachi; Takumi Sato
    Proceedings of WALCOM 2026, Lecture Notes in Computer Science, 16444, 371, 385, 2026, [Peer-reviewed]
    International conference proceedings
  • Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
    Alessio Conte; Roberto Grossi; Yasuaki Kobayashi; Kazuhiro Kurita; Davide Rucci; Takeaki Uno; Kunihiro Wasa
    Algorithmica, 87, 9, 1247, 1273, Sep. 2025, [Peer-reviewed]
    English, Scientific journal
  • The Complexity of Maximal Common Subsequence Enumeration
    Giovanni Buzzega; Alessio Conte; Yasuaki Kobayashi; Kazuhiro Kurita; Giulia Punzi
    Proceedings of the ACM on Management of Data, 09 Jun. 2025, [Peer-reviewed]
    Scientific journal
  • Hitting Geodesic Intervals in Structurally Restricted Graphs.
    Tatsuya Gima; Yasuaki Kobayashi; Yuto Okada; Yota Otachi; Hayato Takaike
    Proceedings of IPEC 2025, LIPIcs, 358, 29:1, 29:16, 2025, [Peer-reviewed]
    English, International conference proceedings
  • A Polynomial Delay Algorithm Generating All Potential Maximal Cliques in Triconnected Planar Graphs.
    Alexander Grigoriev; Yasuaki Kobayashi; Hisao Tamaki; Tom C. van der Zanden
    Proceedings of IPEC 2025, LIPIcs, 358, 21:1, 21:17, 2025, [Peer-reviewed]
    English, International conference proceedings
  • Structural Parameterizations of k-Planarity.
    Tatsuya Gima; Yasuaki Kobayashi; Yuto Okada
    Proceedings of GD 2025, LIPIcs vol. 357, 16:1, 16:17, 2025, [Peer-reviewed]
    International conference proceedings
  • Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints.
    Yasuaki Kobayashi; Kazuhiro Kurita; Kevin Mann; Yasuko Matsui; Hirotaka Ono
    Algorithms, 18, 2, 112, 112, 2025, [Peer-reviewed]
    Scientific journal
  • Broadcasting Under Structural Restrictions.
    Yudai Egami; Tatsuya Gima; Tesshu Hanaka; Yasuaki Kobayashi; Michael Lampis; Valia Mitsou; Edouard Nemery; Yota Otachi; Manolis Vasilakis; Daniel Vaz
    Proceedings of MFCS 2025, 42:1, 42:18, 2025, [Peer-reviewed]
    International conference proceedings
  • Enumeration of Ordered Trees with Leaf Restrictions.
    Yasuaki Kobayashi; Dominik Köppl; Yasuko Matsui; Hirotaka Ono; Toshiki Saitoh; Yushi Uno
    From Strings to Graphs, and Back Again, 8, 19, 2025, [Peer-reviewed]
    English, International conference proceedings
  • On the complexity of list H-packing for sparse graph classes.
    Tatsuya Gima; Tesshu Hanaka; Yasuaki Kobayashi; Yota Otachi; Tomohito Shirai; Akira Suzuki; Yuma Tamura; Xiao Zhou
    Theor. Comput. Sci., 1052, 115425, 115425, 2025, [Peer-reviewed]
    Scientific journal
  • Recognizing 2-Layer and Outer k-Planar Graphs.
    Yasuaki Kobayashi; Yuto Okada; Alexander Wolff
    Proc. of SoCG 2025, LIPIcs, 332, 65:1, 65:16, 2025, [Peer-reviewed]
    International conference proceedings
  • Polynomial-delay enumeration of large maximal common independent sets in two matroids and beyond.
    Yasuaki Kobayashi; Kazuhiro Kurita; Kunihiro Wasa
    Inf. Comput., 304, 105282, 105282, 2025, [Peer-reviewed]
    Scientific journal
  • Finding a minimum spanning tree with a small non-terminal set.
    Tesshu Hanaka; Yasuaki Kobayashi
    Theor. Comput. Sci., 1033, 115092, 115092, 2025, [Peer-reviewed]
    Scientific journal
  • Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints.
    Yasuaki Kobayashi; Kazuhiro Kurita; Kunihiro Wasa
    Discrete Applied Mathematics, 361, 258, 275, 2025, [Peer-reviewed]
    Scientific journal
  • Structural parameterizations of vertex integrity.
    Tatsuya Gima; Tesshu Hanaka; Yasuaki Kobayashi; Ryota Murai; Hirotaka Ono; Yota Otachi
    Theoretical Computer Science, 1024, 114954, 114954, 2025, [Peer-reviewed]
    English, Scientific journal
  • Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited.
    Tatsuya Gima; Takehiro Ito; Yasuaki Kobayashi; Yota Otachi
    Algorithmica, 86, 11, 3395, 3424, Nov. 2024, [Peer-reviewed]
    English, Scientific journal
  • On the complexity of finding a spanning even tree in a graph.
    Tesshu Hanaka; Yasuaki Kobayashi; Kazuhiro Kurita; Yasuko Matsui; Atsuki Nagao; Hirotaka Ono; Kazuhisa Seto
    CoRR, abs/2412.17307, 2024
    Scientific journal
  • Structural Parameterizations of Vertex Integrity.
    Tatsuya Gima; Tesshu Hanaka; Yasuaki Kobayashi; Ryota Murai; Hirotaka Ono; Yota Otachi
    WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation (WALCOM), 406, 420, Springer, 2024, [Peer-reviewed]
    International conference proceedings
  • Basis Sequence Reconfiguration in the Union of Matroids.
    Tesshu Hanaka; Yuni Iwamasa; Yasuaki Kobayashi; Yuto Okada; Rin Saito
    ISAAC, 322, 38:1, 38:16, 2024, [Peer-reviewed]
    English, International conference proceedings
  • Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints.
    Yasuaki Kobayashi; Kazuhiro Kurita; Yasuko Matsui; Hirotaka Ono
    IWOCA, 232, 246, 2024, [Peer-reviewed]
    International conference proceedings
  • Finding Diverse Strings and Longest Common Subsequences in a Graph.
    Yuto Shida; Giulia Punzi; Yasuaki Kobayashi; Takeaki Uno; Hiroki Arimura
    CPM, 27:1, 27:19, 2024, [Peer-reviewed]
    International conference proceedings
  • Parameterized Complexity of Finding Dissimilar Shortest Paths.
    Ryo Funayama; Yasuaki Kobayashi; Takeaki Uno
    CoRR, abs/2402.14376, 2024
    Scientific journal
  • Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover.
    Takashi Horiyama; Yasuaki Kobayashi; Hirotaka Ono; Kazuhisa Seto; Ryu Suzuki
    AAAI, 20726, 20734, 2024, [Peer-reviewed]
    International conference proceedings
  • On the Complexity of List H-Packing for Sparse Graph Classes.
    Tatsuya Gima; Tesshu Hanaka; Yasuaki Kobayashi; Yota Otachi; Tomohito Shirai; Akira Suzuki; Yuma Tamura; Xiao Zhou
    Proceedings of WALCOM 2024, 421, 435, 2024, [Peer-reviewed]
    International conference proceedings
  • Finding a Reconfiguration Sequence between Longest Increasing Subsequences.
    Yuuki Aoike; Masashi Kiyomi; Yasuaki Kobayashi; Yota Otachi
    IEICE Trans. Inf. Syst., 107, 4, 559, 563, The Institute of Electronics, Information and Communication Engineers, 01 Apr. 2024, [Peer-reviewed]
    English, Scientific journal, In this note, we consider the problem of finding a step-by-step transformation between two longest increasing subsequences in a sequence, namely Longest Increasing Subsequence Reconfiguration. We give a polynomial-time algorithm for deciding whether there is a reconfiguration sequence between two longest increasing subsequences in a sequence. This implies that Independent Set Reconfiguration and Token Sliding are polynomial-time solvable on permutation graphs, provided that the input two independent sets are largest among all independent sets in the input graph. We also consider a special case, where the underlying permutation graph of an input sequence is bipartite. In this case, we give a polynomial-time algorithm for finding a shortest reconfiguration sequence (if it exists).
  • Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph.
    Hiroki Arimura; Shunsuke Inenaga; Yasuaki Kobayashi; Yuto Nakashima; Mizuki Sue
    Proceedings of SPIRE 2023, LNCS, 12240, 28, 34, 2023, [Peer-reviewed]
    English, International conference proceedings
  • Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids.
    Yasuaki Kobayashi; Kazuhiro Kurita; Kunihiro Wasa
    Proceedings of MFCS 2023, LIPIcs, 58, 1, 14, 2023, [Peer-reviewed]
    International conference proceedings
  • Reconfiguration of Time-Respecting Arborescences.
    Takehiro Ito; Yuni Iwamasa; Naoyuki Kamiyama; Yasuaki Kobayashi; Yusuke Kobayashi; Shun-ichi Maezawa; Akira Suzuki
    Proceedings of WADS 2023, LNCS, 14079, 521, 532, 2023, [Peer-reviewed]
    English, International conference proceedings
  • A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems.
    Tesshu Hanaka; Masashi Kiyomi; Yasuaki Kobayashi; Yusuke Kobayashi; Kazuhiro Kurita; Yota Otachi
    Proceedings of AAAI 2023, 3968, 3976, 2023, [Peer-reviewed]
    English, International conference proceedings
  • Reconfiguring (non-spanning) arborescences
    Takehiro Ito; Yuni Iwamasa; Yasuaki Kobayashi; Yu Nakahata; Yota Otachi; Kunihiro Wasa
    Theoretical Computer Science, 943, 131, 141, Elsevier BV, Dec. 2022, [Peer-reviewed], [International Magazine]
    English, Scientific journal
  • Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study
    Tesshu Hanaka; Yasuaki Kobayashi; Kazuhiro Kurita; See Woo Lee; Yota Otachi
    Proceedings of the AAAI Conference on Artificial Intelligence, 36, 4, 3758, 3766, Association for the Advancement of Artificial Intelligence (AAAI), 28 Jun. 2022, [Peer-reviewed]
    Scientific journal, Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study the following type of problems: given an integer k, the problem asks for k solutions such that the sum of pairwise (weighted) Hamming distances between these solutions is maximized. Such solutions are called diverse solutions. We present a polynomial-time algorithm for finding diverse shortest st-paths in weighted directed graphs. Moreover, we study the diverse version of other classical combinatorial problems such as diverse weighted matroid bases, diverse weighted arborescences, and diverse bipartite matchings. We show that these problems can be solved in polynomial time as well. To evaluate the practical performance of our algorithm for finding diverse shortest st-paths, we conduct a computational experiment with synthetic and real-world instances. The experiment shows that our algorithm successfully computes diverse solutions within reasonable computational time.
  • Linear-Delay Enumeration for Minimal Steiner Problems
    Yasuaki Kobayashi; Kazuhiro Kurita; Kunihiro Wasa
    Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 301, 313, ACM, 12 Jun. 2022, [Peer-reviewed]
    International conference proceedings
  • Polynomial-Delay and Polynomial-Space Enumeration of Large Maximal Matchings
    Yasuaki Kobayashi; Kazuhiro Kurita; Kunihiro Wasa
    Proceedings of WG 2022, LNCS, 13453, 342, 355, 2022, [Peer-reviewed]
    English, International conference proceedings
  • Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited.
    Tatsuya Gima; Takehiro Ito; Yasuaki Kobayashi; Yota Otachi
    Proceedings of ESA 2022, LIPIcs, 244, 61, 1, 15, 2022, [Peer-reviewed]
    English, International conference proceedings
  • Independent Set Reconfiguration on Directed Graphs.
    Takehiro Ito; Yuni Iwamasa; Yasuaki Kobayashi; Yu Nakahata; Yota Otachi; Masahiro Takahashi; Kunihiro Wasa
    Proceedings of MFCS 2022, LIPIcs, 241, 58, 1, 15, 2022, [Peer-reviewed]
    English, International conference proceedings
  • Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets.
    Ankit Abhinav; Susobhan Bandopadhyay; Aritra Banik; Yasuaki Kobayashi; Shunsuke Nagano; Yota Otachi; Saket Saurabh
    Proceedings of MFCS 2022, LIPIcs, 241, 6, 1, 15, 2022, [Peer-reviewed]
    English, International conference proceedings
  • Parameterized Complexity of Graph Burning.
    Yasuaki Kobayashi; Yota Otachi
    Algorithmica, 84, 8, 2379, 2393, 2022, [Peer-reviewed]
    Scientific journal
  • Exploring the gap between treedepth and vertex cover through vertex integrity.
    Tatsuya Gima; Tesshu Hanaka; Masashi Kiyomi; Yasuaki Kobayashi; Yota Otachi
    Theor. Comput. Sci., 918, 60, 76, 2022, [Peer-reviewed]
    Scientific journal
  • An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion.
    Yuuki Aoike; Tatsuya Gima; Tesshu Hanaka; Masashi Kiyomi; Yasuaki Kobayashi; Yusuke Kobayashi; Kazuhiro Kurita; Yota Otachi
    Theory Comput. Syst., 66, 2, 502, 515, 2022, [Peer-reviewed]
    English, Scientific journal
  • An O(n2)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position.
    Yasuaki Kobayashi; Shin-ichi Nakano; Kei Uchizawa; Takeaki Uno; Yutaro Yamaguchi; Katsuhisa Yamanaka
    IEICE Trans. Inf. Syst., 105, 3, 503, 507, 2022, [Peer-reviewed]
    English, Scientific journal
  • 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, 84, 4, 871, 895, 2022, [Peer-reviewed]
    English, Scientific journal
  • Reconfiguration of Regular Induced Subgraphs
    Eto, H.; Ito, T.; Kobayashi, Y.; Otachi, Y.; Wasa, K.
    Proceedings of WALCOM 2022, 13174 LNCS, 35, 46, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2022, [Peer-reviewed]
    English, Scientific journal
  • Reconfiguring Directed Trees in a Digraph.
    Takehiro Ito; Yuni Iwamasa; Yasuaki Kobayashi; Yu Nakahata; Yota Otachi; Kunihiro Wasa
    Proceedings of COCOON 2021, LNCS, 13025, 343, 354, Springer, 2021, [Peer-reviewed]
    English, International conference proceedings
  • A (probably) optimal algorithm for Bisection on bounded-treewidth graphs.
    Tesshu Hanaka; Yasuaki Kobayashi; Taiga Sone
    Theor. Comput. Sci., 873, 38, 46, 2021, [Peer-reviewed]
    English, Scientific journal
  • Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity.
    Tatsuya Gima; Tesshu Hanaka; Masashi Kiyomi; Yasuaki Kobayashi; Yota Otachi
    Proceedings of CIAC 2021, LNCS, 12701, 271, 285, Springer, 2021, [Peer-reviewed]
    English, International conference proceedings, For intractable problems on graphs of bounded treewidth, two graph parameters
    treedepth and vertex cover number have been used to obtain fine-grained
    complexity results. Although the studies in this direction are successful, we
    still need a systematic way for further investigations because the graphs of
    bounded vertex cover number form a rather small subclass of the graphs of
    bounded treedepth. To fill this gap, we use vertex integrity, which is placed
    between the two parameters mentioned above. For several graph problems, we
    generalize fixed-parameter tractability results parameterized by vertex cover
    number to the ones parameterized by vertex integrity. We also show some finer
    complexity contrasts by showing hardness with respect to vertex integrity or
    treedepth.
  • Finding a maximum minimal separator: Graph classes and fixed-parameter tractability.
    Tesshu Hanaka; Yasuaki Kobayashi; Yusuke Kobayashi; Tsuyoshi Yagita
    Theor. Comput. Sci., 865, 131, 140, 2021, [Peer-reviewed]
    English, Scientific journal, We study the problem of finding a maximum cardinality minimal separator of a
    graph. This problem is known to be NP-hard even for bipartite graphs. In this
    paper, we strengthen this hardness by showing that for planar bipartite graphs,
    the problem remains NP-hard. Moreover, for co-bipartite graphs and for line
    graphs, the problem also remains NP-hard. On the positive side, we give an
    algorithm deciding whether an input graph has a minimal separator of size at
    least $k$ that runs in time $2^{O(k)}n^{O(1)}$. We further show that a
    subexponential parameterized algorithm does not exist unless the Exponential
    Time Hypothesis (ETH) fails. Finally, we discuss a lower bound for polynomial
    kernelizations of this problem.
  • Finding Diverse Trees, Paths, and More.
    Tesshu Hanaka; Yasuaki Kobayashi; Kazuhiro Kurita; Yota Otachi
    Proceedings of AAAI 2021, 3778, 3786, AAAI Press, 2021, [Peer-reviewed]
    English, International conference proceedings, Mathematical modeling is a standard approach to solve many real-world
    problems and {\em diversity} of solutions is an important issue, emerging in
    applying solutions obtained from mathematical models to real-world problems.
    Many studies have been devoted to finding diverse solutions. Baste et al.
    (Algorithms 2019, IJCAI 2020) recently initiated the study of computing diverse
    solutions of combinatorial problems from the perspective of fixed-parameter
    tractability. They considered problems of finding $r$ solutions that maximize
    some diversity measures (the minimum or sum of the pairwise Hamming distances
    among them) and gave some fixed-parameter tractable algorithms for the diverse
    version of several well-known problems, such as {\sc Vertex Cover}, {\sc
    Feedback Vertex Set}, {\sc $d$-Hitting Set}, and problems on bounded-treewidth
    graphs. In this work, we investigate the (fixed-parameter) tractability of
    problems of finding diverse spanning trees, paths, and several subgraphs. In
    particular, we show that, given a graph $G$ and an integer $r$, the problem of
    computing $r$ spanning trees of $G$ maximizing the sum of the pairwise Hamming
    distances among them can be solved in polynomial time. To the best of the
    authors' knowledge, this is the first polynomial-time solvable case for finding
    diverse solutions of unbounded size.
  • 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, 83, 5, 1421, 1458, 2021, [Peer-reviewed]
    English, Scientific journal, The cut-set $\partial(S)$ of a graph $G=(V,E)$ is the set of edges that have
    one endpoint in $S\subset V$ and the other endpoint in $V\setminus S$, and
    whenever $G[S]$ is connected, the cut $[S,V\setminus S]$ of $G$ is called a
    connected cut. A bond of a graph $G$ is an inclusion-wise minimal disconnecting
    set of $G$, i.e., bonds are cut-sets that determine cuts $[S,V\setminus S]$ of
    $G$ such that $G[S]$ and $G[V\setminus S]$ are both connected. Contrasting with
    a large number of studies related to maximum cuts, there exist very few results
    regarding the largest bond of general graphs. In this paper, we aim to reduce
    this gap on the complexity of computing the largest bond, and the maximum
    connected cut of a graph. Although cuts and bonds are similar, we remark that
    computing the largest bond and the maximum connected cut of a graph tends to be
    harder than computing its maximum cut. We show that it does not exist a
    constant-factor approximation algorithm to compute the largest bond, unless P =
    NP. Also, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are
    NP-hard even for planar bipartite graphs, whereas \textsc{Maximum Cut} is
    trivial on bipartite graphs and polynomial-time solvable on planar graphs. In
    addition, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are
    NP-hard on split graphs, and restricted to graphs of clique-width $w$ they can
    not be solved in time $f(w)\times n^{o(w)}$ unless the Exponential Time
    Hypothesis fails, but they can be solved in time $f(w)\times n^{O(w)}$.
    Finally, we show that both problems are fixed-parameter tractable when
    parameterized by the size of the solution, the treewidth, and the twin-cover
    number.
  • On Structural Parameterizations of Node Kayles
    Kobayashi, Y.
    Proceedings of JCDCGGG 2018, 13034 LNCS, 96, 105, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2021, [Peer-reviewed]
    English, Scientific journal
  • Parameterized Complexity of Graph Burning.
    Yasuaki Kobayashi; Yota Otachi
    Proceedings of IPEC 2020, LIPIcs, 180, 21:1, 21:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dec. 2020, [Peer-reviewed]
    English, International conference proceedings
  • An Optimal Algorithm for Bisection for Bounded-Treewidth Graph
    Tesshu Hanaka; Yasuaki Kobayashi; Taiga Sone
    Proceedings of FAW 2020, LNCS, 12340, 25, 36, Springer, Nov. 2020, [Peer-reviewed]
    English, International conference proceedings, The maximum/minimum bisection problems are, given an edge-weighted graph, to
    find a bipartition of the vertex set into two sets whose sizes differ by at
    most one, such that the total weight of edges between the two sets is
    maximized/minimized. Although these two problems are known to be NP-hard, there
    is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen
    et al. (SIAM J. Comput. 2005) gave an $O(2^tn^3)$-time algorithm when given a
    tree decomposition of width $t$ of the input graph, where $n$ is the number of
    vertices of the input graph. Eiben et al. (ESA 2019) improved the running time
    to $O(8^tt^5n^2\log n)$. Moreover, they showed that there is no
    $O(n^{2-\varepsilon})$-time algorithm for trees under some reasonable
    complexity assumption.
    In this paper, we show an $O(2^t(tn)^2)$-time algorithm for both problems,
    which is asymptotically tight to their conditional lower bound. We also show
    that the exponential dependency of the treewidth is asymptotically optimal
    under the Strong Exponential Time Hypothesis. Moreover, we discuss the
    (in)tractability of both problems with respect to special graph classes.
  • Parameterized Complexity of $(A,\ell)$-Path Packing
    Rémy Belmonte; Tesshu Hanaka; Masaaki Kanzaki; Masashi Kiyomi; Yasuaki Kobayashi; Yusuke Kobayashi; Michael Lampis; Hirotaka Ono; Yota Otachi
    Lecture Notes in Computer Science (IWOCA 2020), 43, 55, Springer International Publishing, 08 Aug. 2020, [Peer-reviewed]
    English, International conference proceedings, Given a graph $G = (V,E)$, $A \subseteq V$, and integers $k$ and $\ell$, the
    \textsc{$(A,\ell)$-Path Packing} problem asks to find $k$ vertex-disjoint paths
    of length $\ell$ that have endpoints in $A$ and internal points in $V \setminus
    A$. We study the parameterized complexity of this problem with parameters
    $|A|$, $\ell$, $k$, treewidth, pathwidth, and their combinations. We present
    sharp complexity contrasts with respect to these parameters. Among other
    results, we show that the problem is polynomial-time solvable when $\ell \le
    3$, while it is NP-complete for constant $\ell \ge 4$. We also show that the
    problem is W[1]-hard parameterized by pathwidth${}+|A|$, while it is
    fixed-parameter tractable parameterized by treewidth${}+\ell$.
  • Metric Learning for Ordered Labeled Trees with pq-grams
    Hikaru Shindo; Masaaki Nishino; Yasuaki Kobayashi; Akihiro Yamamoto
    Frontiers in Artificial Intelligence and Applications, 325, 1475, 1482, IOS Press, Aug. 2020, [Peer-reviewed]
    English, International conference proceedings
  • Efficient Enumerations for Minimal Multicuts and Multiway Cuts
    Kazuhiro Kurita; Yasuaki Kobayashi
    Proceedings of MFCS 2020, 60:1, 60:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Aug. 2020, [Peer-reviewed]
    English, International conference proceedings, Let G = (V, E) be an undirected graph and let B ⊆ V × V be a set of terminal pairs. A node/edge multicut is a subset of vertices/edges of G whose removal destroys all the paths between every terminal pair in B. The problem of computing a minimum node/edge multicut is NP-hard and extensively studied from several viewpoints. In this paper, we study the problem of enumerating all minimal node multicuts. We give an incremental polynomial delay enumeration algorithm for minimal node multicuts, which extends an enumeration algorithm due to Khachiyan et al. (Algorithmica, 2008) for minimal edge multicuts.
    Important special cases of node/edge multicuts are node/edge multiway cuts, where the set of terminal pairs contains every pair of vertices in some subset T ⊆ V, that is, B = T × T. We improve the running time bound for this special case: We devise a polynomial delay and exponential space enumeration algorithm for minimal node multiway cuts and a polynomial delay and space enumeration algorithm for minimal edge multiway cuts.
  • 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, 82, 12, 3566, 3587, Springer Science and Business Media LLC, 2020, [Peer-reviewed]
    English, Scientific journal
  • Parameterized algorithms for maximum cut with connectivity constraints
    Hiroshi Eto; Tesshu Hanaka; Yasuaki Kobayashi; Yusuke Kobayashi
    Leibniz International Proceedings in Informatics, LIPIcs, 148, 13:1, 13:15, Dec. 2019, [Peer-reviewed]
    English, International conference proceedings
  • On the complexity of lattice puzzles
    Yasuaki Kobayashi; Koki Suetsugu; Hideki Tsuiki; Ryuhei Uehara
    Leibniz International Proceedings in Informatics, LIPIcs, 149, 32:1, 32:12, Dec. 2019, [Peer-reviewed]
    English, International conference proceedings
  • Automatic Source Code Summarization with Extended Tree-LSTM
    Yusuke Shido; Yasuaki Kobayashi; Akihiro Yamamoto; Atsushi Miyamoto; Tadayuki Matsumura
    Proceedings of the International Joint Conference on Neural Networks, 2019-July, Jul. 2019, [Peer-reviewed]
    English, International conference proceedings
  • An improved fixed-parameter algorithm for max-cut parameterized by crossing number
    Yasuaki Kobayashi; Yusuke Kobayashi; Shuichi Miyazaki; Suguru Tamaki
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11638 LNCS, 327, 338, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2019, [Peer-reviewed]
    English, International conference proceedings
  • Algorithms and Hardness Results for the Maximum Balanced Connected Subgraph Problem
    Yasuaki Kobayashi; Kensuke Kojima; Norihide Matsubara; Taiga Sone; Akihiro Yamamoto
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11949 LNCS, 303, 315, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2019, [Peer-reviewed]
    International conference proceedings
  • An improved fixed-parameter algorithm for one-page crossing minimization
    Yasuaki Kobayashi; Hiromu Ohtsuka; Hisao Tamaki
    Leibniz International Proceedings in Informatics, LIPIcs, 89, 25:1, 25:12, 01 Feb. 2018, [Peer-reviewed]
    English, International conference proceedings
  • Treedepth parameterized by vertex cover number
    Yasuaki Kobayashi; Hisao Tamaki
    Leibniz International Proceedings in Informatics, LIPIcs, 63, 18:1, 18-11, 01 Feb. 2017, [Peer-reviewed]
    English, International conference proceedings
  • Improved methods for computing distances between unordered trees using integer programming
    Eunpyeong Hong; Yasuaki Kobayashi; Akihiro Yamamoto
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10628 LNCS, 45, 60, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2017, [Peer-reviewed]
    English, International conference proceedings
  • A faster fixed parameter algorithm for two-layer crossing minimization
    Yasuaki Kobayashi; Hisao Tamaki
    Information Processing Letters, 116, 9, 547, 549, 01 Sep. 2016, [Peer-reviewed]
    English, Scientific journal
  • Computing Directed Pathwidth in O(1. 89 n) Time
    Kenta Kitsunai; Yasuaki Kobayashi; Keita Komuro; Hisao Tamaki; Toshihiro Tano
    Algorithmica, 75, 1, 138, 157, 01 May 2016, [Peer-reviewed]
    English, Scientific journal
  • A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
    Yasuaki Kobayashi; Hisao Tamaki
    Algorithmica, 72, 3, 778, 790, 12 Jul. 2015, [Peer-reviewed]
    English, Scientific journal
  • Computing the pathwidth of directed graphs with small vertex cover
    Yasuaki Kobayashi
    Information Processing Letters, 115, 2, 310, 312, Feb. 2015, [Peer-reviewed]
    English, Scientific journal
  • On the pathwidth of almost semicomplete digraphs
    Kenta Kitsunai; Yasuaki Kobayashi; Hisao Tamaki
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9294, 816, 827, 2015, [Peer-reviewed]
    English, International conference proceedings
  • A linear edge kernel for two-layer crossing minimization
    Yasuaki Kobayashi; Hirokazu Maruta; Yusuke Nakae; Hisao Tamaki
    Theoretical Computer Science, 554, C, 74, 81, 2014, [Peer-reviewed]
    English, Scientific journal
  • Search space reduction through commitments in pathwidth computation: An experimental study
    Yasuaki Kobayashi; Keita Komuro; Hisao Tamaki
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8504 LNCS, 388, 399, 2014, [Peer-reviewed]
    English, International conference proceedings
  • A linear edge kernel for two-layer crossing minimization
    Yasuaki Kobayashi; Hirokazu Maruta; Yusuke Nakae; Hisao Tamaki
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7936 LNCS, 458, 468, 2013, [Peer-reviewed]
    English, International conference proceedings
  • A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization
    Yasuaki Kobayashi; Hisao Tamaki
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7501 LNCS, 683, 694, 2012, [Peer-reviewed]
    English, International conference proceedings
  • Computing directed pathwidth in O(1.89n) time
    Kenta Kitsunai; Yasuaki Kobayashi; Keita Komuro; Hisao Tamaki; Toshihiro Tano
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7535 LNCS, 182, 193, 2012, [Peer-reviewed]
    English, International conference proceedings
  • k-cyclic orientations of graphs
    Yasuaki Kobayashi; Yuichiro Miyamoto; Hisao Tamaki
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6507 LNCS, PART 2, 73, 84, 2010, [Peer-reviewed]
    English, International conference proceedings
■ Other Activities and Achievements
■ Syllabus
  • 情報知識ネットワーク特論, 2024年, 修士課程, 情報科学院
  • 情報知識ネットワーク特論, 2024年, 博士後期課程, 情報科学研究科
  • 情報知識ネットワーク特論, 2024年, 博士後期課程, 情報科学院
  • 情報理論, 2024年, 学士課程, 工学部
  • 情報理工学実験Ⅰ, 2024年, 学士課程, 工学部
  • 情報理工学実験Ⅱ, 2024年, 学士課程, 工学部
  • 計算理論, 2024年, 学士課程, 工学部
■ Research Themes
  • Making treewidth and pathwidth practical
    Grants-in-Aid for Scientific Research
    01 Apr. 2024 - 31 Mar. 2028
    玉木 久夫; 齋藤 寿樹; 大舘 陽太; 川原 純; 吉仲 亮; 小林 靖明
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (A), Meiji University, 24H00697
  • 解空間の形状に着目した組合せ遷移の理論：計算量解析の高精細化とソルバー新技法
    科学研究費助成事業
    01 Apr. 2024 - 31 Mar. 2028
    伊藤 健洋; 宋 剛秀; 小林 靖明; 野崎 雄太
    日本学術振興会, 基盤研究(A), 東北大学, 24H00686
  • Foundation of algorithmic theory of finding diverse solutions for discrete optimization problems
    Grants-in-Aid for Scientific Research
    01 Apr. 2023 - 31 Mar. 2028
    小林 靖明
    研究課題である離散最適化問題に対する多様な解の発見するアルゴリズムに関して，最短路問題における多様性最大化，充足可能性問題，最長共通部分文字列問題に関する多様性最大化問題に取り組み，理論的にシャープな結果を得ることができた．最短路問題に関しては，Fominらの結果 (STACS 2023)のアイデアを部分的に用いて，固定パラメータアルゴリズムを設計し，そのアルゴリズム的成果が理論的にタイトであることを示した．充足可能性問題に関しては，Schaeferが示したいくつかの「容易な」論理式のクラスに関して，その多様性最大化板の問題が「2つの遠い解」を見つける問題に限定しても難しいことを示した．最長共通部分文字列問題に関しては，小林のこれまでの研究 (AAAI 2021, AAAI 2022)で得られた成果をうまく適用することにより，厳密アルゴリズムや近似アルゴリズムを設計することに成功した．これらの成果は国内研究会にて発表を行い，さらに国際会議に投稿中である．また，それらの研究の過程において，組合せ遷移問題 (有向木の遷移問題，最長増加部分列の遷移問題)，列挙問題 (マトロイド共通基の列挙問題) グラフの構造パラメータを用いたアルゴリズム (頂点インテグリティの計算，部分グラフのリスト詰め込み問題，頂点被覆の唯一化の問題) に関していくつか研究成果を得ることができたため，それらを論文にまとめ国際会議および論文誌に採択された．特に，グラフの頂点インテグリティと呼ばれるグラフパラメータを計算するアルゴリズムについては，国際会議WALCOM 2024において最優秀論文賞に選出された．
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Hokkaido University, 23K28034
  • 離散最適化問題に対する多様な解発見のためのアルゴリズム理論基盤の構築
    科学研究費助成事業 基盤研究(B)
    01 Apr. 2023 - 31 Mar. 2028
    小林 靖明
    日本学術振興会, 基盤研究(B), 北海道大学, 23H03344
  • Development of Next-generation Semi-Structured Data Mining Technology Towards The Real-World Knowledge Creation Infrastructure
    Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
    01 Apr. 2020 - 31 Mar. 2025
    有村 博紀; 宇野 毅明; 平田 耕一; 山本 章博; 喜田 拓也; ジョーダン チャールズハロルド; 小林 靖明
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (A), Hokkaido University, 20H00595
  • 高次元ブール値テンソルデータからの多項閉集合を用いた知識発見
    科学研究費助成事業
    01 Apr. 2021 - 31 Mar. 2024
    山本 章博; 小林 靖明
    日本学術振興会, 基盤研究(B), 京都大学, 21H03499
  • 計算機科学アプローチによる組合せ遷移の展開：アルゴリズムの自動生成に向けて
    科学研究費助成事業 学術変革領域研究(B)
    02 Oct. 2020 - 31 Mar. 2023
    伊藤 健洋; 大舘 陽太; 小林 靖明; 和佐 州洋
    2020年10月の交付内定からすぐにオンラインでの研究打合せを開始し，本計画研究班の研究目的を改めて研究分担者らと共有した．また，2020年11月と12月には，対面を含む打合せも開催した．そして，具体的に取り組むべき研究として，まずはMouawadらが与えた単項二階述語論理を用いたメタ定理を精査した．このメタ定理は，Courcelleが1990年に組合せ遷移問題ではない問題に対して開発したメタ定理を基にしており，組合せ遷移問題に特有の遷移系列をどのように扱うことで，Mouawadらがメタ定理を開発したのかを重点的に解析した．その結果，遷移系列の長さをパラメータとしている点が，Mouawadらのメタ定理では非常に強く作用していることが判明した．これは，ある意味で，扱う問題の遷移系列の長さに制限があるといえる．そこで本計画研究班では，この遷移系列の長さをパラメータから外すことができないかを議論し，その検討を進めている．
    また，C01班との連携も開始しており，特に「非対称的な遷移」に関するアルゴリズム研究に力を入れた．これまで研究されてきた組合せ遷移問題のほとんどは，対称的な遷移を扱っており，非対称的な遷移は従来研究の一般化となっている．我々は，具体的には，有向グラフにおける独立集合の遷移問題に取り組み，その計算困難性と容易性について解析を進めた．
    この他にも，列挙アルゴリズムや指数時間アルゴリズムなど，近接分野の代表的なアルゴリズム手法を組合せ遷移問題へ適用できないか考察を行った．
    日本学術振興会, 学術変革領域研究(B), 東北大学, 20H05793
  • グラフの木分解を用いた高速なメタアルゴリズムの研究
    科学研究費助成事業 若手研究
    01 Apr. 2020 - 31 Mar. 2023
    小林 靖明
    本研究の目的であるグラフの幅パラメータを用いたアルゴリズム的メタ定理に向けての研究を行った．具体的には，グラフの幅パラメータとして最も成功している，木幅をより制限することにより，様々な問題の固定パラメータ容易性を示した．これらは，グラフの木幅をパラメータとしてもW[1]困難性を示すことができ，既存のメタ定理を用いて解くことができない問題群であり，それらを解くための新たなメタ定理の表現方法に関して知見を得ることができた．
    また，既存のメタ定理で扱っているような最適化問題やモデル検査問題だけでなく，列挙問題や組合せ遷移問題に対してメタ定理の可能性を検討した．この過程において，既存の疎グラフに対するアルゴリズム的メタ定理の既存の方法を包括的にサーベイし，列挙問題や組合せ遷移問題に対するアルゴリズム的メタ定理への知見やその実現可能性を得ることができた．
    本研究テーマから得た知見を生かして，人工知能分野で研究される問題についても取り組んだ．具体的には最適化問題の解の多様性の研究にも取り組んだ．これらの問題は古典的な最適化問題の一般化になっており，応用の観点と計算量理論の観点でいずれも興味深く，これらの問題に集中的に取り組みいくつかの結果を得て国内外の会議で発表を行った．
    日本学術振興会, 若手研究, 京都大学, 20K19742
  • Properties of Weakly Closed Itemsets and their Application to Knowledge Discovery
    Grants-in-Aid for Scientific Research
    01 Apr. 2017 - 31 Mar. 2020
    Yamamoto Akihiro
    In this research, in order to admit noise in closed sets in a binary relation between two discrete-valued attributes, we formulated weakly closed sets using set theory and constructed an algorithm for enumerating weakly closed sets. We defined weakly closed sets based on the fact that closed sets can be interpreted using graphs. We designed an algorithm for enumerating weakly closed sets with modifying the well-known fast enumeration algorithm for closed sets. Furthermore, by modifying the definition of weakly closed sets and the enumeration algorithm to the trajectory data collected from travelers, we succeeded in enumerating the routes frequently followed by them as weakly closed sets. We also showed that the fixpoint semantics of closed sets cannot be given to weakly closed sets in general.
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Kyoto University, 17H01788
  • Knowledge Discovery Methods based on Closed Set Construction for Data with Attributes Whose Values are from Ordered Sets
    Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    01 Apr. 2014 - 31 Mar. 2017
    Yamamoto Akihiro; AVIS David; KOBAYASHI Yasuaki; IKEDA Madori; OTAKI Keisuke; KARIYAMA Kazuaki; YAMAZAKI Tomoya; NISHIMURA Shoichi
    The goal of this research is to develop methods for knowledge discovery that uses both orders for attribute values and closed sets of from mixed data. Since knowledge discovery by closed set is one kind of technique called bi-clustering of binary relational data, we obtained a method for bi-clustering for matrix factorization and search of matrices. Also we analyzed relationship between closed sets obtained by various bi-clustering method. Moreover, we developed methods for principal component analysis of the tree structure using the partial order of the substructure of tree data, the thesaurus expansion using the order relation of the vocabulary in the natural language thesaurus, and discovery methods of the similarity of the tree structure data with the integer programming.
    Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (B), Kyoto University, 26280085
  • Exact algorithms for Sugiyama method in layered graph drawings
    Grants-in-Aid for Scientific Research Grant-in-Aid for Research Activity start-up
    29 Aug. 2014 - 31 Mar. 2016
    Yasuaki Kobayashi
    In this research, we apply exact algorithms to a well-known layered graph drawing technique, called Sugiyama method. Although several heuristic approaches are known for this method, no exact approach is known in the literature. Our experimental study shows that the state-of-the-art fixed parameter algorithm for minimizing the number of crossings is substantially applicable to reasonable-sized instances.Moreover, we give a new fixed parameter algorithm for the two-layer case, which improves the running time of the previously known fixed parameter algorithm.
    Japan Society for the Promotion of Science, Grant-in-Aid for Research Activity start-up, Gakushuin University, 26880018