小林 靖明 (コバヤシ ヤスアキ)
| 情報科学研究院 情報理工学部門 知識ソフトウェア科学分野 | 准教授 |
Last Updated :2025/06/22
■研究者基本情報
Researchmap個人ページ
研究者番号
- 60735083
J-Global ID
■研究活動情報
受賞
論文
- 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, 2025年06月09日, ［査読有り］
研究論文（学術雑誌） - Recognizing 2-Layer and Outer k-Planar Graphs.
Yasuaki Kobayashi, Yuto Okada, Alexander Wolff 0001
Proc. of SoCG 2025, LIPIcs, 332, 65:1, 65:16, 2025年, ［査読有り］
研究論文（国際会議プロシーディングス） - Polynomial-delay enumeration of large maximal common independent sets in two matroids and beyond.
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
Inf. Comput., 304, 105282, 2025年, ［査読有り］
研究論文（学術雑誌） - Finding a minimum spanning tree with a small non-terminal set.
Tesshu Hanaka, Yasuaki Kobayashi
Theor. Comput. Sci., 1033, 115092, 2025年, ［査読有り］
研究論文（学術雑誌） - 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年, ［査読有り］
研究論文（学術雑誌） - Structural parameterizations of vertex integrity.
Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otachi
Theor. Comput. Sci., 1024, 114954, 2025年, ［査読有り］
英語, 研究論文（学術雑誌） - Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited.
Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi
Algorithmica, 86, 11, 3395, 3424, 2024年11月, ［査読有り］
英語, 研究論文（学術雑誌） - 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年
研究論文（学術雑誌） - 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年, ［査読有り］
研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
研究論文（国際会議プロシーディングス） - Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size.
Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Davide Rucci, Takeaki Uno, Kunihiro Wasa
CoRR, abs/2405.13613, 2024年
研究論文（学術雑誌） - 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年, ［査読有り］
研究論文（国際会議プロシーディングス） - Parameterized Complexity of Finding Dissimilar Shortest Paths.
Ryo Funayama, Yasuaki Kobayashi, Takeaki Uno
CoRR, abs/2402.14376, 2024年
研究論文（学術雑誌） - 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年, ［査読有り］
研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
研究論文（国際会議プロシーディングス） - 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, 2024年04月01日, ［査読有り］
英語, 研究論文（学術雑誌）, 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - Reconfiguring (non-spanning) arborescences
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa
Theoretical Computer Science, 943, 131, 141, Elsevier BV, 2022年12月, ［査読有り］, ［国際誌］
英語, 研究論文（学術雑誌） - 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), 2022年06月28日, ［査読有り］
研究論文（学術雑誌）, 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, 2022年06月12日, ［査読有り］
研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - Parameterized Complexity of Graph Burning.
Yasuaki Kobayashi, Yota Otachi
Algorithmica, 84, 8, 2379, 2393, 2022年, ［査読有り］
研究論文（学術雑誌） - 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年, ［査読有り］
研究論文（学術雑誌） - 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年, ［査読有り］
英語, 研究論文（学術雑誌） - 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年, ［査読有り］
英語, 研究論文（学術雑誌） - 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年, ［査読有り］
英語, 研究論文（学術雑誌） - 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年, ［査読有り］
英語, 研究論文（学術雑誌） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - A (probably) optimal algorithm for Bisection on bounded-treewidth graphs.
Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
Theor. Comput. Sci., 873, 38, 46, 2021年, ［査読有り］
英語, 研究論文（学術雑誌） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, 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年, ［査読有り］
英語, 研究論文（学術雑誌）, 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, 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年, ［査読有り］
英語, 研究論文（学術雑誌）, 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年, ［査読有り］
英語, 研究論文（学術雑誌） - 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, 2020年12月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - An Optimal Algorithm for Bisection for Bounded-Treewidth Graph
Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
Proceedings of FAW 2020, LNCS, 12340, 25, 36, Springer, 2020年11月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, 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, 2020年08月08日, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, 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, 2020年08月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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, 2020年08月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）, 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年, ［査読有り］
英語, 研究論文（学術雑誌） - 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, 2019年12月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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, 2019年12月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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, 2019年07月, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
研究論文（国際会議プロシーディングス） - 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, 2018年02月01日, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - Treedepth parameterized by vertex cover number
Yasuaki Kobayashi, Hisao Tamaki
Leibniz International Proceedings in Informatics, LIPIcs, 63, 18:1, 18-11, 2017年02月01日, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - A faster fixed parameter algorithm for two-layer crossing minimization
Yasuaki Kobayashi, Hisao Tamaki
Information Processing Letters, 116, 9, 547, 549, 2016年09月01日, ［査読有り］
英語, 研究論文（学術雑誌） - Computing Directed Pathwidth in O(1. 89 n) Time
Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano
Algorithmica, 75, 1, 138, 157, 2016年05月01日, ［査読有り］
英語, 研究論文（学術雑誌） - A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
Yasuaki Kobayashi, Hisao Tamaki
Algorithmica, 72, 3, 778, 790, 2015年07月12日, ［査読有り］
英語, 研究論文（学術雑誌） - Computing the pathwidth of directed graphs with small vertex cover
Yasuaki Kobayashi
Information Processing Letters, 115, 2, 310, 312, 2015年02月, ［査読有り］
英語, 研究論文（学術雑誌） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（学術雑誌） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス） - 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年, ［査読有り］
英語, 研究論文（国際会議プロシーディングス）
その他活動・業績
- 木分解を用いた組合せ最適化問題に対する局所探索の高速化
後出祥臣, 儀間達也, 小林靖明, 情報処理学会研究報告(Web), 2025, AL-201, 2025年 - 辺カット型グラフパラメータに基づく最大出次数最小化問題と標的集合選択問題の計算複雑性
藤原優, 儀間達也, 小林靖明, 情報処理学会研究報告(Web), 2024, AL-199, 2024年 - マトロイドの基の組の遷移問題
土中哲秀, 岩政勇仁, 小林靖明, 岡田優斗, 斉藤凜, 電子情報通信学会技術研究報告(Web), 124, 223(COMP2024 13-19), 2024年 - 連結制約のある頂点符号付きグラフ分割問題の緩和問題に対する高速なアルゴリズム
藤原 優, 吉岡 和希, 小林 靖明, 人工知能学会研究会資料 人工知能基本問題研究会, 126, 44, 48, 2023年11月15日
一般社団法人 人工知能学会, 日本語 - 要素数制約付き極小辺被覆の多項式遅延列挙
小林 靖明, 栗田 和宏, 人工知能学会研究会資料 人工知能基本問題研究会, 126, 39, 43, 2023年11月15日
一般社団法人 人工知能学会, 日本語 - 組合せゲームにおけるアルゴリズムと計算量—特集 パズルの発想
小林 靖明, オペレーションズ・リサーチ = Communications of the Operations Research Society of Japan : 経営の科学, 68, 3, 131, 137, 2023年03月
日本オペレーションズ・リサーチ学会, 日本語 - 特集：「人工知能分野における博士論文—博士論文に見る研究テーマの動向—」特集「人工知能分野における博士論文—博士論文に見る研究テーマの動向—」にあたって
小林 靖明, 伏見 卓恭, 人工知能, 38, 1, 45, 45, 2023年01月01日
一般社団法人 人工知能学会, 日本語 - 文字列集合に対する多様な最長共通部分列の発見
志田祐仁, 有村博紀, 小林靖明, 電子情報通信学会技術研究報告(Web), 123, 325(COMP2023 16-27), 2023年 - 多様な最短経路を求める固定パラメータアルゴリズム
舟山諒, 小林靖明, 電子情報通信学会技術研究報告(Web), 123, 325(COMP2023 16-27), 2023年 - 最大最小k-パス頂点被覆問題
HANAKA Tesshu, KOBAYASHI Yasuaki, KURITA Kazuhiro, 情報処理学会研究報告(Web), 2023, AL-192, 2023年 - 要素数制約付き極大マトロイド共通独立集合の多項式遅延列挙
小林靖明, 栗田和宏, 和佐州洋, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2023, 2023年 - 弦グラフの部分クラスにおける極大誘導部分グラフ列挙への多項式遅延アルゴリズム
佐藤嶺, 小林靖明, 栗田和宏, 和佐州洋, 電子情報通信学会技術研究報告(Web), 123, 325(COMP2023 16-27), 2023年 - Reconfiguration of Time-Respecting Arborescences.
Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki, CoRR, abs/2305.07262, 2023年 - Minimum Consistent Subset for Trees Revisited.
Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi, Hiroomi Nochide, Yota Otachi, CoRR, abs/2305.07259, 2023年 - 多様な解集合を発見する効率良い近似アルゴリズム
栗田 和宏, 土中 哲秀, 清見 礼, 小林 靖明, 小林 佑輔, 大舘 陽太, 人工知能学会研究会資料 人工知能基本問題研究会, 119, 21, 26, 2022年01月20日
一般社団法人 人工知能学会, 日本語 - 平面グラフ中の辺連結度制約付き全域部分グラフの効率良い列挙
KOBAYASHI Yasuaki, KURITA Kazuhiro, WASA Kunihiro, 電子情報通信学会技術研究報告(Web), 122, 229(COMP2022 13-20), 2022年 - 正則誘導部分グラフ遷移問題の計算複雑さ
江藤宏, 伊藤健洋, 小林靖明, 大舘陽太, 和佐州洋, 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2022, 2022年 - 半順序集合の弱埋め込み問題に対するパラメータ化アルゴリズム
宮崎怜子, 有村博紀, 小林靖明, 電子情報通信学会技術研究報告(Web), 122, 294(COMP2022 21-32), 2022年 - コンパクト非巡回語グラフに基づく連長圧縮Burrows-Wheeler変換の効率良い構築
須江瑞樹, 小林靖明, 有村博紀, 中島祐人, 稲永俊介, 電子情報通信学会技術研究報告(Web), 122, 294(COMP2022 21-32), 2022年 - Independent set reconfiguration on directed graphs.
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa, CoRR, abs/2203.13435, 2022年 - 多様な組合せを求めるためのアルゴリズム論的アプローチ
小林 靖明, システム・制御・情報 = Systems, control and information : システム制御情報学会誌, 66, 11, 415, 420, 2022年
システム制御情報学会, 日本語 - 特集：「人工知能分野における博士論文—博士論文に見る研究テーマの動向—」特集「人工知能分野における博士論文—博士論文に見る研究テーマの動向—」にあたって
小林 靖明, 山本 泰生, 人工知能, 37, 1, 56, 56, 2022年01月01日
一般社団法人 人工知能学会, 日本語 - Finding shortest non-separating and non-disconnecting paths.
Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, CoRR, abs/2202.09718, 2022年 - カテゴリカル変数の背後にある構造を利用した決定木学習の困難さ
小林 靖明, 小林 佑輔, 大舘 陽太, 人工知能学会研究会資料 人工知能基本問題研究会, 117, 02, 2021年09月20日
In decision tree learning, we split an instance space into two subspaces based on a of instances at each node. For numerical or ordinal categorical features, this can be done by an "optimal" hyperplane that separates the domain space of those features. For nominal categorical features, however, it is not obvious to define a "hyperplane" of the domain space. Lucena (Lucena, AISTAT 2020) pointed out that the domain space of nominal categorical features may be structured and exploited this structural information to learn decision trees. In this method, at each internal node, we need to find an "optimal" bipartition of a graph whose vertices are labeled by either +1 or ?1 such that both sides are connected and the misclassification is minimized. In this paper, we formalize this problem as Connected Bipartition and investigate its computational complexity., 一般社団法人 人工知能学会, 日本語 - 省メモリなトップK列挙アルゴリズムの設計技法
小林 靖明, 栗田 和宏, 人工知能学会研究会資料 人工知能基本問題研究会, 117, 06, 2021年09月20日
One way to measure the efficiency of enumeration algorithms is to evaluate it with respect to the input size and the number of solutions. Since the number of solutions can be typically exponentially larger than the size of the input, the running time of an enumeration algorithm is huge even if we manage to design an extremely efficient enumeration algorithm. However, in realworld problems, it is not always necessary to enumerate all the solutions and it may be required to enumerate sufficiently many "good" solutions. In such a situation, top-k enumeration algorithms are of great importance in many areas. On the theoretical side, Lawler (Lawler, Management Science 1972) developed a general framework for designing efficient top-k enumeration algorithms. The outline of Lawler's framework is a kind of best-first search. By using this framework, we can design a top-k enumeration algorithm that works in space linear with respect to k, where k is the number of solutions we wish to enumerate. However, since k may be exponentially larger than the input size n, the algorithm needs a huge amount of memory if k is large. In this paper, we modify Lawler's framework and obtain a space-efficient framework that runs in space depending only on a polynomial in n., 一般社団法人 人工知能学会, 日本語 - 疎グラフに対するアルゴリズム的メタ定理
小林靖明, RAMP数理最適化シンポジウム論文集, 33rd, 2021年 - 特集「人工知能分野における博士論文—博士論文に見る研究テーマの動向—」にあたって
山本 泰生, 小林 靖明, 人工知能, 36, 1, 60, 60, 2021年01月01日
一般社団法人 人工知能学会, 日本語 - 区間順序上の最長増加部分列
青池宥希, 清見礼, 小林靖明, 大舘陽太, 情報処理学会研究報告(Web), 2021, AL-184, 2021年 - 順列グラフのカラフル独立集合問題に対するアルゴリズム
吉村仁志, 小林靖明, 山本章博, 情報処理学会研究報告(Web), 2021, AL-182, 2021年 - 大きな極大マッチングの多項式遅延列挙
栗田 和宏, 小林 靖明, 和佐 州洋, 人工知能学会全国大会論文集, abs/2105.04146, 2E1OS13a03, 2E1OS13a03, 2021年
私たちは与えられた閾値t より大きな要素数を持つ極大マッチングの列挙に対して，2つの多項式遅延列挙アルゴリズムを与える．まず1つ目のアルゴリズムはそのような全てのマッチングをO(m2)遅延で列挙する．ここで，mはグラフ中の辺の本数である．この結果は既存の極大マッチング列挙に対して，要素数制約を追加した結果である．2つ目のアルゴリズムは全ての極大マッチングを要素数が非増加の順序で列挙するアルゴリズムであり，これも多項式遅延で動作する．, 一般社団法人 人工知能学会, 日本語 - Metric Learning for Ordered Labeled Trees with pq-grams.
Hikaru Shindo, Masaaki Nishino, Yasuaki Kobayashi, Akihiro Yamamoto, CoRR, abs/2003.03960, 2020年 - Parameterized Complexity of Graph Burning.
Yasuaki Kobayashi, Yota Otachi, CoRR, abs/2007.08811, 2020年 - Computing the Largest Bond and the Maximum Connected Cut of a Graph.
Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Uéverton S. Souza, CoRR, abs/2007.04513, 2020年 - 特集「人工知能分野における博士論文—博士論文に見る研究テーマの動向—」にあたって
山本 泰生, 小林 靖明, 人工知能, 35, 1, 79, 79, 2020年01月01日
一般社団法人 人工知能学会, 日本語 - 多様な部分グラフを発見するアルゴリズム
HAKANA Tesshu, KOBAYASHI Yasuaki, KURITA Kazuhiro, OTACHI Yota, 人工知能学会人工知能基本問題研究会資料, 113th, 06, 2020年
一般社団法人 人工知能学会, 日本語 - Polynomial Delay Enumeration for Minimal Steiner Problems.
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa, CoRR, abs/2010.11462, 2020年
Let $G = (V, E)$ be a undirected graph and let $W \subseteq V$ be a set of
terminals. A \emph{Steiner subgraph} of $(G, W)$ is a subgraph of $G$ that
contains all vertices of $W$ and there is a path between every pair of vertices
of $W$ in the subgraph. We say that a Steiner subgraph is minimal if it has no
proper Steiner subgraph. It is easy to observe that every minimal Steiner
subgraph forms a tree, which is called a minimal Steiner tree. We propose a
linear delay and polynomial space algorithm for enumerating all minimal Steiner
trees of $(G, W)$, which improves a previously known polynomial delay
enumeration algorithm in [Kimelfeld and Sagiv, Inf. Syst., 2008]. Our
enumeration algorithm can be extended to other Steiner problems: minimal
Steiner forests, minimal terminal Steiner trees, minimal directed Steiner
trees. As another variant of the minimal Steiner subgraph problem, we study the
problem of enumerating minimal induced Steiner subgraphs. We propose a
polynomial delay and exponential space enumeration algorithm of minimal induced
Steiner subgraphs for claw-free graphs, whereas the problem on general graphs
is shown to be at least as hard as the problem of enumerating minimal
transversals in hypergraphs. Contrary to these tractable results, we show that
the problem of enumerating minimal group Steiner trees is at least as hard as
the minimal transversal enumeration problem on hypergraphs. - A Note on Exponential-Time Algorithms for Linearwidth.
Yasuaki Kobayashi, Yu Nakahata, CoRR, abs/2010.02388, 2020年
In this note, we give an algorithm that computes the linearwidth of input
$n$-vertex graphs in time $O^*(2^n)$, which improves a trivial $O^*(2^m)$-time
algorithm, where $n$ and $m$ the number of vertices and edges, respectively. - Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Cardinality Constraints.
Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa, CoRR, abs/2009.08830, 2020年
A property $\Pi$ on a finite set $U$ is \emph{monotone} if for every $X
\subseteq U$ satisfying $\Pi$, every superset $Y \subseteq U$ of $X$ also
satisfies $\Pi$. Many combinatorial properties can be seen as monotone
properties, and the problem of finding a minimum subset of $U$ satisfying $\Pi$
is a central problem in combinatorial optimization. Although many
approximate/exact algorithms have been developed to solve this problem on
numerous properties, a solution obtained by these algorithms is often
unsuitable for real-world applications due to the difficulty of building
mathematical models on real-world problems. A promising approach to overcome
this difficulty is to \emph{enumerate} multiple small solutions rather than to
\emph{find} a single small solution. To this end, given an integer $k$, we
devise algorithms that \emph{approximately} enumerate all minimal subsets of
$U$ with cardinality at most $k$ satisfying $\Pi$ for various monotone
properties $\Pi$, where "approximate enumeration" means that algorithms may
output some minimal subsets satisfying $\Pi$ whose cardinality exceeds $k$ and
is at most $ck$ for some constant $c \ge 1$. These algorithms allow us to
efficiently enumerate minimal vertex covers, minimal dominating sets in bounded
degree graphs, minimal feedback vertex sets, minimal hitting sets in bounded
rank hypergraphs, etc., with constant approximation factors. - 可換マッチング問題の固定パラメーター容易性に関する研究
久保田稜, 小林靖明, 小島健介, 山本章博, 人工知能学会人工知能基本問題研究会資料, 112th, 61, 66, 2020年
人工知能学会, 日本語 - An FPT Algorithm for Max-Cut Parameterized by Crossing Number
Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki, arXiv, 2019年04月10日
The Max-Cut problem is known to be NP-hard on general graphs, while it can be
solved in polynomial time on planar graphs. In this paper, we present a
fixed-parameter tractable algorithm for the problem on `almost' planar graphs:
Given an $n$-vertex graph and its drawing with $k$ crossings, our algorithm
runs in time $O(2^k(n+k)^{3/2} \log (n + k))$. Previously, Dahn, Kriege and
Mutzel (IWOCA 2018) obtained an algorithm that, given an $n$-vertex graph and
its $1$-planar drawing with $k$ crossings, runs in time $O(3^k n^{3/2} \log
n)$. Our result simultaneously improves the running time and removes the
$1$-planarity restriction. - 半順序集合の次元を求める固定パラメータアルゴリズム
小林靖明, 電子情報通信学会技術研究報告, 119, 21(COMP2019 1-9)(Web), 2019年 - コンテキストと構文の情報を用いたニューラルネットによる変数名予測
松田浩幸, 紫藤佑介, 小林靖明, 山本章博, 宮本篤志, 松村忠幸, 情報処理学会研究報告(Web), 2019, SE-202, 2019年 - グラフの2等分割問題に対するアルゴリズムと計算複雑性
小林靖明, 曽根大雅, 土中哲秀, 電子情報通信学会技術研究報告, 119, 314(MSS2019 23-40), 41, 46, 2019年
電子情報通信学会, 日本語 - 構造的パラメータを用いた頂点Kaylesの解析
小林靖明, 電子情報通信学会技術研究報告, 118, 216(COMP2018 9-20)(Web), 2018年 - トークンのN-gramによるプログラム表現を用いたコードクローン検出手法
向井達郎, 小林靖明, 紫藤佑介, 山本章博, 宮本篤志, 松村忠幸, 嶺竜治, 情報処理学会研究報告(Web), 2018, SE-199, 2018年 - モジュラリティを基準とした関係データに対する特徴選択 (特集 「SAT技術の理論,実装,応用」および一般)
紫藤 佑介, 山本 章博, 小林 靖明, 久保山 哲二, 人工知能基本問題研究会, 103, 89, 94, 2017年03月13日
人工知能学会, 日本語 - クラスタ構造を仮定した場合の双クラスタリングアルゴリズムの解析 (特集 「SAT技術の理論,実装,応用」および一般)
山浦 智佳子, 小林 靖明, 山本 章博, 久保山 哲二, 人工知能基本問題研究会, 103, 67, 72, 2017年03月13日
人工知能学会, 日本語 - グラフのカット幅を求める高速な厳密アルゴリズムの開発
小林靖明, 学習院大学計算機センター年報, 37, 2017年 - 交差数の少ない単一ページ描画における固定パラメータアルゴリズム
大塚広夢, 小林靖明, 玉木久夫, 情報処理学会研究報告(Web), 2017, AL-161, 2017年 - 最小フィルイン問題に対する安全なセパレータについて
小林靖明, 玉木久夫, 情報処理学会研究報告(Web), 2017, AL-164, 2017年 - 整数計画法による木間距離の計算を高速化するための新しい定式化
HONG Eunpyeong, 小林靖明, 山本章博, 人工知能学会人工知能基本問題研究会資料, 103rd, 78, 83, 2017年
人工知能学会, 日本語 - 頂点被覆数が小さいグラフの最適消去木の計算について (システム数理と応用)
小林 靖明, 玉木 久夫, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 115, 316, 53, 58, 2015年11月20日
電子情報通信学会, 日本語 - 準完全有向グラフとその一般化に対するパス幅計算について
橘内 謙太, 小林 靖明, 玉木 久夫, 情報処理学会研究報告. AL, アルゴリズム研究会報告, 2015, 3, 1, 8, 2015年02月24日
有向グラフ G は,その各頂点 u が 「辺 (u,v) も辺 (v,u) も存在しないような頂点 v≠u の個数は高々 h である」 という性質を満たすとき,h 準完全であるという.0 準完全な有向グラフは準完全有向グラフとして知られ,トーナメントはその特別な場合である.本稿では,n 頂点の h 準完全有向グラフ G と正整数 k が与えられたとき,G のパス幅が k 以下であるかを判定する (h+2k+1)2knO(1) 時間のアルゴリズムを与える.この結果は,Pilipczuk の準完全有向グラフに対する結果を (n に対する依存度の犠牲のもとに) 一般化している.我々のアルゴリズムは劣モジュラシステムにおける線形配置問題に対する Nagamochi のアルゴリズムを有向グラフのパス幅問題に特化し,我々の目的のために適合させたものである.「U を 入次数 (出次数) が k 以下であるような任意の頂点集合とするとき,U∪{v} の入次数 (出次数) が k 以下であるような頂点 v の個数は高々 b である」 という性質を満たす有向グラフに対してこのアルゴリズムの実行時間は b2knO(1) である., 一般社団法人情報処理学会, 日本語 - Improved fixed parameter algorithm for two-layer crossing minimization
Yasuaki Kobayashi, Hisao Tamaki, 研究報告アルゴリズム（AL）, 2015, 9, 1, 2, 2015年01月06日
We give an algorithm that decides whether the bipartite crossing number of a given graph is at most k. The running time of the algorithm is 2O(k)nO(1), where n is the number of vertices of the input graph, which improves the previous algorithm due to Kobayashi et al. (TCS 2014) that runs in 2O(k log k)nO(1) time. This result is based on a combinarotial upper bound on the number of two-layer drawings of a connected bipartite graph with a bounded crossing number.We give an algorithm that decides whether the bipartite crossing number of a given graph is at most k. The running time of the algorithm is 2O(k)nO(1), where n is the number of vertices of the input graph, which improves the previous algorithm due to Kobayashi et al. (TCS 2014) that runs in 2O(k log k)nO(1) time. This result is based on a combinarotial upper bound on the number of two-layer drawings of a connected bipartite graph with a bounded crossing number., 一般社団法人情報処理学会, 英語 - <研究報告>教員のICT機器利用支援のための動画講習教材の作成と評価
大野 志郎, 横山 悦郎, 城所 弘泰, 伊藤 大河, 小林 靖明, 学習院大学計算機センター年報, 36, 36, 81, 88, 2015年01月01日
日本語 - Search space reduction through commitments in pathwidth computation: an experimental study
Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, 研究報告アルゴリズム（AL）, 2014, 15, 1, 6, 2014年06月06日
In designing an XP algorithm for pathwidth of digraphs, Tamaki introduced the notion of commitments and used them to reduce the search space with naively O(n!) states to one with nO(k) states, where n is the number of vertices and k is the pathwidth of the given digraph. The goal of the current work is to evaluate the potential of commitments in heuristic algorithms for the pathwidth of undirected graphs that are aimed to work well in practice even for graphs with large pathwidth. We classify commitments by a simple parameter called depth. Through experiments performed on TreewidthLIB instances, we show that depth-1 commitments are extremely effective in reducing the search space and lead to a practical algorithm capable of computing the pathwidth of many instances for which the exact pathwidth was not previously known. On the other hand, we find that the additional search space reduction enabled by depth-d commitments with 2 ≦ d ≦ 10 is limited and that there is little hope for effective heuristics based on commitments with such depth.In designing an XP algorithm for pathwidth of digraphs, Tamaki introduced the notion of commitments and used them to reduce the search space with naively O(n!) states to one with nO(k) states, where n is the number of vertices and k is the pathwidth of the given digraph. The goal of the current work is to evaluate the potential of commitments in heuristic algorithms for the pathwidth of undirected graphs that are aimed to work well in practice even for graphs with large pathwidth. We classify commitments by a simple parameter called depth. Through experiments performed on TreewidthLIB instances, we show that depth-1 commitments are extremely effective in reducing the search space and lead to a practical algorithm capable of computing the pathwidth of many instances for which the exact pathwidth was not previously known. On the other hand, we find that the additional search space reduction enabled by depth-d commitments with 2 ≦ d ≦ 10 is limited and that there is little hope for effective heuristics based on commitments with such depth., 一般社団法人情報処理学会, 英語 - Computing the pathwidth of directed graphs with small vertex cover
Yasuaki Kobayashi, 研究報告アルゴリズム（AL）, 2014, 16, 1, 2, 2014年06月06日
We give an algorithm that computes the pathwidth of a given directed graph D in 3τ(D)nO(1) time where n is the number of vertices of D and τ(D) is the number of vertices of a minimum vertex cover of the underlying graph of D. This result extends that of [Chapelle et al., 2013] for undirected graphs to directed graphs. Moreover, our algorithm is based on a standard dynamic programming with a simple tree-pruning trick, which is extremely simple and easy to implement.We give an algorithm that computes the pathwidth of a given directed graph D in 3γ(D)nO(1) time where n is the number of vertices of D and γ(D) is the number of vertices of a minimum vertex cover of the underlying graph of D. This result extends that of [Chapelle et al., 2013] for undirected graphs to directed graphs. Moreover, our algorithm is based on a standard dynamic programming with a simple tree-pruning trick, which is extremely simple and easy to implement., 一般社団法人情報処理学会, 英語 - A Linear Edge Kernel for Two-Layer Crossing Minimization (コンピュテーション)
KOBAYASHI YASUAKI, MARUTA HIROKAZU, NAKAE YUSUKE, TAMAKI HISAO, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 113, 50, 21, 24, 2013年05月17日
We consider a simple generalization of two-layer crossing minimization problem (TLCM) called leafedge-weighted TLCM (LEW-TLCM), where we allow positive weights on edges incident to leaves, and show that this problem admits a kernel with O(k) edges provided that the given graph is connected. As a straightforward consequence, LEW-TLCM (and hence TLCM) has a fixed parameter algorithm that runs in 2^ - A Linear Edge Kernel for Two-Layer Crossing Minimization
Yasuaki Kobayashi, Hirokazu Maruta, Yusuke Nakae, Hisao Tamaki, 研究報告アルゴリズム（AL）, 2013, 4, 1, 4, 2013年05月10日
We consider a simple generalization of two-layer crossing minimization problem (TLCM) called leaf-edge-weighted TLCM (LEW-TLCM), where we allow positive weights on edges incident to leaves, and show that this problem admits a kernel with O(k) edges provided that the given graph is connected. As a straightforward consequence, LEW-TLCM (and hence TLCM) has a fixed parameter algorithm that runs in 2O(k log k) + nO(1) time which improves on the previously best known algorithm with running time 2O(k3)n.We consider a simple generalization of two-layer crossing minimization problem (TLCM) called leaf-edge-weighted TLCM (LEW-TLCM), where we allow positive weights on edges incident to leaves, and show that this problem admits a kernel with O(k) edges provided that the given graph is connected. As a straightforward consequence, LEW-TLCM (and hence TLCM) has a fixed parameter algorithm that runs in 2O(k log k) + nO(1) time which improves on the previously best known algorithm with running time 2O(k3)n., 一般社団法人情報処理学会, 英語 - k-cyclic Orientations of Graphs (アルゴリズム(AL) Vol.2011-AL-134)
Yasuaki Kobayashi, Yuichiro Miyamoto, Hisao Tamaki, 研究報告アルゴリズム（AL）, 2011, 6, 1, 8, 2011年02月28日
An orientation of an undirected graph G is a directed graph, with same vertex set, whose underlying graph is G. For integer k ≥ 3, we say a directed graph D is k-cyclic if every edge of D belongs to a directed cycle in D of length at most k. We consider the problem of deciding if a given graph has a k-cyclic orientation. We show that this problem is NP-complete for every fixed k ≥ 3 for general graphs and for every fixed k ≥ 4 for planar graphs. We give a polynomial time algorithm for planar graphs with k = 3, which constructs a 3-cyclic orientation when the answer is affirmative.An orientation of an undirected graph G is a directed graph, with same vertex set, whose underlying graph is G. For integer k ≥ 3, we say a directed graph D is k-cyclic if every edge of D belongs to a directed cycle in D of length at most k. We consider the problem of deciding if a given graph has a k-cyclic orientation. We show that this problem is NP-complete for every fixed k ≥ 3 for general graphs and for every fixed k ≥ 4 for planar graphs. We give a polynomial time algorithm for planar graphs with k = 3, which constructs a 3-cyclic orientation when the answer is affirmative., 情報処理学会, 英語
共同研究・競争的資金等の研究課題
- 木幅・パス幅計算の実用化
科学研究費助成事業
2024年04月01日 - 2028年03月31日
玉木 久夫, 齋藤 寿樹, 大舘 陽太, 川原 純, 吉仲 亮, 小林 靖明
日本学術振興会, 基盤研究(A), 明治大学, 24H00697 - 解空間の形状に着目した組合せ遷移の理論：計算量解析の高精細化とソルバー新技法
科学研究費助成事業
2024年04月01日 - 2028年03月31日
伊藤 健洋, 宋 剛秀, 小林 靖明, 野崎 雄太
日本学術振興会, 基盤研究(A), 東北大学, 24H00686 - 離散最適化問題に対する多様な解発見のためのアルゴリズム理論基盤の構築
科学研究費助成事業 基盤研究(B)
2023年04月01日 - 2028年03月31日
小林 靖明
日本学術振興会, 基盤研究(B), 北海道大学, 23H03344 - 実世界知識基盤形成のための次世代半構造マイニング技術の発展
科学研究費助成事業 基盤研究(A)
2020年04月01日 - 2025年03月31日
有村 博紀, 宇野 毅明, 平田 耕一, 山本 章博, 喜田 拓也, ジョーダン チャールズハロルド, 小林 靖明
日本学術振興会, 基盤研究(A), 北海道大学, 20H00595 - 高次元ブール値テンソルデータからの多項閉集合を用いた知識発見
科学研究費助成事業
2021年04月01日 - 2024年03月31日
山本 章博, 小林 靖明
日本学術振興会, 基盤研究(B), 京都大学, 21H03499 - 計算機科学アプローチによる組合せ遷移の展開：アルゴリズムの自動生成に向けて
科学研究費助成事業 学術変革領域研究(B)
2020年10月02日 - 2023年03月31日
伊藤 健洋, 大舘 陽太, 小林 靖明, 和佐 州洋
2020年10月の交付内定からすぐにオンラインでの研究打合せを開始し，本計画研究班の研究目的を改めて研究分担者らと共有した．また，2020年11月と12月には，対面を含む打合せも開催した．そして，具体的に取り組むべき研究として，まずはMouawadらが与えた単項二階述語論理を用いたメタ定理を精査した．このメタ定理は，Courcelleが1990年に組合せ遷移問題ではない問題に対して開発したメタ定理を基にしており，組合せ遷移問題に特有の遷移系列をどのように扱うことで，Mouawadらがメタ定理を開発したのかを重点的に解析した．その結果，遷移系列の長さをパラメータとしている点が，Mouawadらのメタ定理では非常に強く作用していることが判明した．これは，ある意味で，扱う問題の遷移系列の長さに制限があるといえる．そこで本計画研究班では，この遷移系列の長さをパラメータから外すことができないかを議論し，その検討を進めている．
また，C01班との連携も開始しており，特に「非対称的な遷移」に関するアルゴリズム研究に力を入れた．これまで研究されてきた組合せ遷移問題のほとんどは，対称的な遷移を扱っており，非対称的な遷移は従来研究の一般化となっている．我々は，具体的には，有向グラフにおける独立集合の遷移問題に取り組み，その計算困難性と容易性について解析を進めた．
この他にも，列挙アルゴリズムや指数時間アルゴリズムなど，近接分野の代表的なアルゴリズム手法を組合せ遷移問題へ適用できないか考察を行った．
日本学術振興会, 学術変革領域研究(B), 東北大学, 20H05793 - グラフの木分解を用いた高速なメタアルゴリズムの研究
科学研究費助成事業 若手研究
2020年04月01日 - 2023年03月31日
小林 靖明
本研究の目的であるグラフの幅パラメータを用いたアルゴリズム的メタ定理に向けての研究を行った．具体的には，グラフの幅パラメータとして最も成功している，木幅をより制限することにより，様々な問題の固定パラメータ容易性を示した．これらは，グラフの木幅をパラメータとしてもW[1]困難性を示すことができ，既存のメタ定理を用いて解くことができない問題群であり，それらを解くための新たなメタ定理の表現方法に関して知見を得ることができた．
また，既存のメタ定理で扱っているような最適化問題やモデル検査問題だけでなく，列挙問題や組合せ遷移問題に対してメタ定理の可能性を検討した．この過程において，既存の疎グラフに対するアルゴリズム的メタ定理の既存の方法を包括的にサーベイし，列挙問題や組合せ遷移問題に対するアルゴリズム的メタ定理への知見やその実現可能性を得ることができた．
本研究テーマから得た知見を生かして，人工知能分野で研究される問題についても取り組んだ．具体的には最適化問題の解の多様性の研究にも取り組んだ．これらの問題は古典的な最適化問題の一般化になっており，応用の観点と計算量理論の観点でいずれも興味深く，これらの問題に集中的に取り組みいくつかの結果を得て国内外の会議で発表を行った．
日本学術振興会, 若手研究, 京都大学, 20K19742 - 弱閉集合の代数的構造の解明と知識発見への応用
科学研究費助成事業 基盤研究(B)
2017年04月01日 - 2020年03月31日
山本 章博, 小林 靖明, 久保山 哲二
本研究は,自然言語データにおける本文とキーワードの関係，Webページ間のリンク構造における参照元と参照先の関係など，２つの離散値属性間の２項関係から部分関係を抽出することによる知識発見を対象とする．研究計画で設定した[課題１]～[課題５]のうち，本年度は，[課題１]閉集合が数学的に定義されているためノイズを許さないため実用に向かないことがある一方，密集合は実応用から提案されたためノイズを許容するものの数学的な定義がない，という相補的な点に着目し，密な部分関係を弱閉集合として集合論的に定式化する[課題３]の弱集合に対して，閉集合と同様の不動点意味論を構成する，[課題５]弱集合の効率的列挙アルゴリズムの開発と実用性検討，の３課題を中心に研究を展開したした．
[課題１]については，閉集合をグラフ理論のことばを用いれば，２部グラフの完全部分グラフという解釈が可能であることに着目し，グラフ理論における完全グラフの定義を弱めたk-Plexという概念を範として，弱集合を(k,l)-閉集合として定式化した．以下では弱集合を(k,l)-閉集合とよぶ．
そして，[課題３]の不動点を構成するための反復関数を，オリジナルの閉集合のための反復関数を修正して定式化した上で，(k,l)-閉集合と反復関数の不動点の関係を与えた．閉集合の場合は，反復関数の不動点と閉集合は１対１に対応するが，(k,l)-閉集合の場合は必ずしも１対１にはならないこと，そもそも反復関数が収束しないことがあることも示した．これらの結果をもとに，[課題５]に取り組み，閉集合の高速列挙アルゴリズムであるLCMを修正することにより，(k,l)-閉集合の列挙が可能であることを示した．このアルゴリズムは，理論上は高速な列挙が不可能な場合もあるが，現実の小規模データに対しては十分高速に列挙することを確認した．
日本学術振興会, 基盤研究(B), 京都大学, 17H01788 - 順序関係が成立する属性を持つデータからの閉集合を用いた知識発見
科学研究費助成事業 基盤研究(B)
2014年04月01日 - 2017年03月31日
山本 章博, 平田 耕一, 伊藤 公人, 久保山 哲二, 吉仲 亮, 小林 靖明, 池田 真土里, 大滝 啓介, 狩山 和亮, 山崎 朋哉, 西村 翔一
本研究の目標は，属性が備える順序関係と閉集合を利用した知識発見手法を開発することであった．閉集合による知識発見は２項関係データの双クラスタリングとよばれる手法の一種であるので，行列の因子分解と探索による閉集合構成，様々な双クラスタリング手法で得られた閉集合間の関係解析を行った．また，木構造データの部分構造間の半順序を用いた木構造の主成分分析手法，自然言語シソーラスにおける語彙の順序関係を用いたシソーラス拡張，整数計画法による木構造の共通部分の高速発見手法という成果を得た．
日本学術振興会, 基盤研究(B), 京都大学, 26280085 - グラフの階層描画におけるSugiyama methodへの厳密アルゴリズムの適用
科学研究費助成事業 研究活動スタート支援
2014年08月29日 - 2016年03月31日
小林 靖明
本研究ではグラフの階層描画の手法として知られるSugiyama methodに対して厳密アルゴリズムの適用を行った．Sugiyama methodに関してはいくつかのヒューリスティックアルゴリズムを用いた方法が知られているが，厳密アルゴリズムを適用する研究は知られていない．本研究の実験において，交差数を最小化する固定パラメータアルゴリズムが十分に有用であることを明らかにした．また，階層を2層に限定した場合について既存のアルゴリズムよりも高速なアルゴリズムの開発に成功した．
日本学術振興会, 研究活動スタート支援, 学習院大学, 26880018
