MF研究者総覧

研究者データベース

詳細
researchmap個人ページ
Last Updated :2024/07/25

研究者情報

マスター

アカウント（マスター）

  • 氏名

    小林　靖明(コバヤシ　ヤスアキ), コバヤシ　ヤスアキ

所属（マスター）

  • 情報科学研究院　情報理工学部門　知識ソフトウェア科学分野

所属（マスター）

  • 情報科学研究院　情報理工学部門　知識ソフトウェア科学分野

researchmap

プロフィール情報

所属

  • 北海道大学

学位

  • 博士（理学）（明治大学）

プロフィール情報

  • 姓

    小林

  • 名

    靖明

  • ID各種

    201601002248769544

所属

  • 北海道大学

業績リスト

研究分野

  • 情報通信 / 数理情報学
  • 情報通信 / 知能情報学
  • 情報通信 / 情報学基礎論

受賞

  • 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横断若手の会研究部会」 学生優秀発表賞

論文

  • AOIKE Yuuki, KIYOMI Masashi, KOBAYASHI Yasuaki, OTACHI Yota
    IEICE Transactions on Information and Systems E107.D 4 559 - 563 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).
  • Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono 0001
    IWOCA 232 - 246 2024年 [査読有り]
  • Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Davide Rucci, Takeaki Uno, Kunihiro Wasa
    CoRR abs/2405.13613 2024年
  • Yuto Shida, Giulia Punzi, Yasuaki Kobayashi, Takeaki Uno, Hiroki Arimura
    CPM 27:1 - 27:19 2024年 [査読有り]
  • Ryo Funayama, Yasuaki Kobayashi, Takeaki Uno
    CoRR abs/2402.14376 2024年
  • Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono, Kazuhisa Seto, Ryu Suzuki
    AAAI 20726 - 20734 2024年 [査読有り]
  • Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou
    Proceedings of WALCOM 2024 421 - 435 2024年 [査読有り]
  • Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otachi
    WALCOM2024, LNCS 14549 406 - 420 2024年 [査読有り]
  • Tesshu Hanaka, Yasuaki Kobayashi
    CoRR abs/2310.05494 2023年
  • Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi, Yuto Nakashima, Mizuki Sue
    Proceedings of SPIRE 2023, LNCS 12240 28 - 34 2023年 [査読有り]
  • Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
    Proceedings of MFCS 2023, LIPIcs 58 1 - 14 2023年 [査読有り]
  • Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki
    Proceedings of WADS 2023, LNCS 14079 521 - 532 2023年 [査読有り]
  • Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi
    Proceedings of AAAI 2023 3968 - 3976 2023年 [査読有り]
  • Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa
    Theoretical Computer Science 943 131 - 141 2022年12月 [査読有り]
  • Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota Otachi
    Proceedings of the AAAI Conference on Artificial Intelligence 36 4 3758 - 3766 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.
  • Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
    Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems 301 - 313 2022年06月12日 [査読有り]
  • Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
    Proceedings of WG 2022, LNCS 13453 342 - 355 2022年 [査読有り]
  • Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi
    Proceedings of ESA 2022, LIPIcs 244 61 1 - 15 2022年 [査読有り]
  • Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa
    Proceedings of MFCS 2022, LIPIcs 241 58 1 - 15 2022年 [査読有り]
  • Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, Saket Saurabh
    Proceedings of MFCS 2022, LIPIcs 241 6 1 - 15 2022年 [査読有り]
  • Yasuaki Kobayashi, Yota Otachi
    Algorithmica 84 8 2379 - 2393 2022年 [査読有り]
  • Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi
    Theor. Comput. Sci. 918 60 - 76 2022年 [査読有り]
  • Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi
    Theory Comput. Syst. 66 2 502 - 515 2022年 [査読有り]
  • Yasuaki Kobayashi, Shin-ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka
    IEICE Trans. Inf. Syst. 105 3 503 - 507 2022年 [査読有り]
  • 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年 [査読有り]
  • Eto, H., Ito, T., Kobayashi, Y., Otachi, Y., Wasa, K.
    Proceedings of WALCOM 2022 13174 LNCS 35 - 46 2022年 [査読有り]
  • Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa
    Proceedings of COCOON 2021, LNCS 13025 343 - 354 2021年 [査読有り]
  • Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
    Theor. Comput. Sci. 873 38 - 46 2021年 [査読有り]
  • Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi
    Proceedings of CIAC 2021, LNCS 12701 271 - 285 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.
  • 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.
  • Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi
    Proceedings of AAAI 2021 3778 - 3786 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.
  • 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.
  • Kobayashi, Y.
    Proceedings of JCDCGGG 2018 13034 LNCS 96 - 105 2021年 [査読有り]
     
    Node Kayles is a well-known two-player impartial game on graphs: Given an undirected graph, each player alternately chooses a vertex not adjacent to previously chosen vertices, and a player who cannot choose a new vertex loses the game. The problem of deciding if the first player has a winning strategy in this game is known to be PSPACE-complete. There are a few studies on algorithmic aspects of this problem. In this paper, we consider the problem from the viewpoint of fixed-parameter tractability. We show that the problem is fixed-parameter tractable parameterized by the size of a minimum vertex cover or the modular-width of a given graph. Moreover, we give a polynomial kernelization with respect to neighborhood diversity.
  • Yasuaki Kobayashi, Yota Otachi
    Proceedings of IPEC 2020, LIPIcs 180 21:1 - 21:10 2020年12月 [査読有り]
  • Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
    Proceedings of FAW 2020, LNCS 12340 25 - 36 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.
  • 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 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$.
  • Hikaru Shindo, Masaaki Nishino, Yasuaki Kobayashi, Akihiro Yamamoto
    Frontiers in Artificial Intelligence and Applications 325 1475 - 1482 2020年08月 [査読有り][通常論文]
  • Kazuhiro Kurita, Yasuaki Kobayashi
    Proceedings of MFCS 2020 60:1 - 60:14 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.
  • Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Tom C. van der Zanden
    Algorithmica 82 12 3566 - 3587 2020年 [査読有り][通常論文]
  • Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi
    Leibniz International Proceedings in Informatics, LIPIcs 148 13:1 - 13:15 2019年12月 [査読有り][通常論文]
     
    © Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi; licensed under Creative Commons License CC-BY. We study two variants of Maximum Cut, which we call Connected Maximum Cut and Maximum Minimal Cut, in this paper. In these problems, given an unweighted graph, the goal is to compute a maximum cut satisfying some connectivity requirements. Both problems are known to be NP-complete even on planar graphs whereas Maximum Cut on planar graphs is solvable in polynomial time. We first show that these problems are NP-complete even on planar bipartite graphs and split graphs. Then we give parameterized algorithms using graph parameters such as clique-width, tree-width, and twin-cover number. Finally, we obtain FPT algorithms with respect to the solution size.
  • Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, Ryuhei Uehara
    Leibniz International Proceedings in Informatics, LIPIcs 149 32:1 - 32:12 2019年12月 [査読有り][通常論文]
     
    © Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, and Ryuhei Uehara; licensed under Creative Commons License CC-BY In this paper, we investigate the computational complexity of lattice puzzle, which is one of the traditional puzzles. A lattice puzzle consists of 2n plates with some slits, and the goal of this puzzle is to assemble them to form a lattice of size n×n. It has a long history in the puzzle society; however, there is no known research from the viewpoint of theoretical computer science. This puzzle has some natural variants, and they characterize representative computational complexity classes in the class NP. Especially, one of the natural variants gives a characterization of the graph isomorphism problem. That is, the variant is GI-complete in general. As far as the authors know, this is the first non-trivial GI-complete problem characterized by a classic puzzle. Like the sliding block puzzles, this simple puzzle can be used to characterize several representative computational complexity classes. That is, it gives us new insight of these computational complexity classes.
  • Yusuke Shido, Yasuaki Kobayashi, Akihiro Yamamoto, Atsushi Miyamoto, Tadayuki Matsumura
    Proceedings of the International Joint Conference on Neural Networks 2019-July 2019年07月 [査読有り][通常論文]
     
    © 2019 IEEE. Neural machine translation models are used to automatically generate a document from given source code since this can be regarded as a machine translation task. Source code summarization is one of the components for automatic document generation, which generates a summary in natural language from given source code. This suggests that techniques used in neural machine translation, such as Long Short-Term Memory (LSTM), can be used for source code summarization. However, there is a considerable difference between source code and natural language: Source code is essentially structured, having loops and conditional branching, etc. Therefore, there is some obstacle to apply known machine translation models to source code.Abstract syntax trees (ASTs) capture these structural properties and play an important role in recent machine learning studies on source code. Tree-LSTM is proposed as a generalization of LSTMs for tree-structured data. However, there is a critical issue when applying it to ASTs: It cannot handle a tree that contains nodes having an arbitrary number of children and their order simultaneously, which ASTs generally have such nodes. To address this issue, we propose an extension of Tree-LSTM, which we call Multi-way Tree-LSTM and apply it for source code summarization. As a result of computational experiments, our proposal achieved better results when compared with several state-of-the-art techniques.
  • 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 2019年 [査読有り][通常論文]
     
    © 2019, Springer Nature Switzerland AG. 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(2k(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(3kn3/2 log n). Our result simultaneously improves the running time and removes the 1-planarity restriction.
  • 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 2019年 [査読有り][通常論文]
     
    © 2019, Springer Nature Switzerland AG. The Balanced Connected Subgraph problem (BCS) was recently introduced by Bhore et al. (CALDAM 2019). In this problem, we are given a graph G whose vertices are colored by red or blue. The goal is to find a maximum connected subgraph of G having the same number of blue vertices and red vertices. They showed that this problem is NP-hard even on planar graphs, bipartite graphs, and chordal graphs. They also gave some positive results: BCS can be solved in time for trees and time for split graphs and properly colored bipartite graphs, where n is the number of vertices and m is the number of edges. In this paper, we show that BCS can be solved in time for trees and time for interval graphs. The former result can be extended to bounded treewidth graphs. We also consider a weighted version of BCS (WBCS). We prove that this variant is weakly NP-hard even on star graphs and strongly NP-hard even on split graphs and properly colored bipartite graphs, whereas the unweighted counterpart is tractable on those graph classes. Finally, we consider an exact exponential-time algorithm for general graphs. We show that BCS can be solved in time. This algorithm is based on a variant of Dreyfus-Wagner algorithm for the Steiner tree problem.
  • Yasuaki Kobayashi, Hiromu Ohtsuka, Hisao Tamaki
    Leibniz International Proceedings in Informatics, LIPIcs 89 25:1 - 25:12 2018年02月01日 [査読有り][通常論文]
     
    © 2018 Yasuaki Kobayashi, Hiromu Ohtsuka, and Hisao Tamaki. Book embedding is one of the most well-known graph drawing models and is extensively studied in the literature. The special case where the number of pages is one is of particular interest: an embedding in this case has a natural circular representation useful for visualization and graphs that can be embedded in one page without crossings form an important graph class, namely that of outerplanar graphs. In this paper, we consider the problem of minimizing the number of crossings in a one-page book embedding, which we call one-page crossing minimization. Here, we are given a graph G with n vertices together with a non-negative integer k and are asked whether G can be embedded into a single page with at most k crossings. Bannister and Eppstein (GD 2014) showed that this problem is fixed-parameter tractable. Their algorithm is derived through the application of Courcelle's theorem (on graph properties definable in the monadic second-order logic of graphs) and runs in f(L)n time, where L = 2O(k2) is the length of the formula defining the property that the one-page crossing number is at most k and f is a computable function without any known upper bound expressible as an elementary function. We give an explicit dynamic programming algorithm with a drastically improved running time of 2O(k log k)n.
  • Yasuaki Kobayashi, Hisao Tamaki
    Leibniz International Proceedings in Informatics, LIPIcs 63 18:1 - 18-11 2017年02月01日 [査読有り][通常論文]
     
    © 2016 Yasuaki Kobayashi and Hisao Tamaki. To solve hard graph problems from the parameterized perspective, structural parameters have commonly been used. In particular, vertex cover number is frequently used in this context. In this paper, we study the problem of computing the treedepth of a given graph G. We show that there are an O(τ(G)3) vertex kernel and an O(4τ(G)τ(G)n) time fixed-parameter algorithm for this problem, where τ(G) is the size of a minimum vertex cover of G and n is the number of vertices of G.
  • 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 2017年 [査読有り][通常論文]
     
    © Springer International Publishing AG 2017. Kondo et al. (DS 2014) proposed integer linear programming formulations for computing the tree edit distance and its variants between unordered rooted trees. They showed that the tree edit distance, segmental distance, and bottom-up segmental distance problems respectively have integer linear programming formulations with O(nm) variables and O(n2m2) constraints, where n and m are the number of nodes of two input trees. In this work, we propose new integer linear programming formulations for these three distances and the bottom-up distance by combining with dynamic programming. For computing the tree edit distance, we solve O(nm) subproblems, each of which is formulated by an integer linear program with O(nm) variables and O(n+ m) constraints. For the other three distances, each subproblem can be reduced to the maximum weight matching problem in a bipartite graph which is solvable in polynomial time. In order to compute the distances from the solutions of subproblems, we also give a unified integer linear formulation with O(nm) variables and O(n+ m) constraints. We conducted a computational experiment to evaluate the performance of our methods. The experimental results show that our methods remarkably outperformed to the previous methods due to Kondo et al.
  • Yasuaki Kobayashi, Hisao Tamaki
    Information Processing Letters 116 9 547 - 549 2016年09月01日 [査読有り][通常論文]
     
    © 2016 Elsevier B.V. All rights reserved. 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 upper bounded by 2O(k)+nO(1), where n is the number of vertices of the input graph, which improves the previously known algorithm due to Kobayashi et al. (TCS 2014) that runs in 2O(klogk)+nO(1) time. This result is based on a combinatorial upper bound on the number of two-layer drawings of a connected bipartite graph with a bounded crossing number.
  • Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano
    Algorithmica 75 1 138 - 157 2016年05月01日 [査読有り][通常論文]
     
    © 2015, Springer Science+Business Media New York. We give an algorithm for computing the directed pathwidth of a digraph with n vertices in O(1. 89 n) time. This is the first algorithm with running time better than the straightforward O∗(2n). As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in O(1. 9657 n) time.
  • Yasuaki Kobayashi, Hisao Tamaki
    Algorithmica 72 3 778 - 790 2015年07月12日 [査読有り][通常論文]
     
    © 2014, The Author(s). We give a subexponential fixed parameter algorithm for one-sided crossing minimization. It runs in $O(k2^{\sqrt{2k } } + n)$ time, where n is the number of vertices of the given graph and parameter k is the number of crossings. The exponent of $O(\sqrt{k})$ in this bound is asymptotically optimal assuming the Exponential Time Hypothesis and the previously best known algorithm runs in $2^{O(\sqrt{k}\log k)} + n^{O(1)}$ time. We achieve this significant improvement by the use of a certain interval graph naturally associated with the problem instance and a simple dynamic program on this interval graph. The linear dependency on n is also achieved through the use of this interval graph.
  • Yasuaki Kobayashi
    Information Processing Letters 115 2 310 - 312 2015年02月 [査読有り][通常論文]
     
    © 2014 Elsevier B.V. All rights reserved. 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 undirected graph of D. This result extends that of [5] 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. An additional advantage of our algorithm is that a minimum vertex cover appears in the analysis but not in the algorithm itself, in contrast to the algorithm of [5] which needs to compute a minimum vertex cover.
  • 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年 [査読有り][通常論文]
     
    © Springer-Verlag Berlin Heidelberg 2015. We call a digraph h-semicomplete if each vertex of the digraph has at most h non-neighbors, where a non-neighbor of a vertex v is a vertex u ≠ v such that there is no edge between u and v in either direction. This notion generalizes that of semicomplete digraphs which are 0-semicomplete and tournaments which are semicomplete and have no anti-parallel pairs of edges. Our results in this paper are as follows. (1) We give an algorithm which, given an h-semicomplete digraph G on n vertices and a positive integer k, in (h + 2k + 1)2knO(1) time either constructs a path-decomposition of G of width at most k or concludes correctly that the pathwidth of G is larger than k. (2) We show that there is a function f(k, h) such that every h-semicomplete digraph of pathwidth at least f(k, h) has a semicomplete subgraph of pathwidth at least k. One consequence of these results is that the problem of deciding if a fixed digraph H is topologically contained in a given h-semicomplete digraph G admits a polynomial-time algorithm for fixed h.
  • Yasuaki Kobayashi, Hirokazu Maruta, Yusuke Nakae, Hisao Tamaki
    Theoretical Computer Science 554 C 74 - 81 2014年 [査読有り][通常論文]
     
    © 2014 Elsevier B.V. The two-layer crossing minimization problem (TLCM), given a bipartite graph G with n vertices and a positive integer k, asks whether G has a two-layer drawing with at most k crossings. We consider a simple generalization of 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(klogk)+nO(1) time which improves on the previously best known algorithm with running time 2O(k3)n.
  • 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年 [査読有り][通常論文]
     
    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 n O(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. © 2014 Springer International Publishing.
  • 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年 [査読有り][通常論文]
     
    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 2 O(k logk) + n O(1) time which improves on the previously best known algorithm with running time. © 2013 Springer-Verlag Berlin Heidelberg.
  • 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年 [査読有り][通常論文]
     
    We give a subexponential fixed parameter algorithm for one-sided crossing minimization. It runs in O(3 √2k + n)time, where n is the number of vertices of the given graph and parameter k is the number of crossings. The exponent of O(√k) in this bound is asymptotically optimal assuming the Exponential Time Hypothesis and the previously best known algorithm runs in 2 O(√k log k) + n O(1) time. We achieve this significant improvement by the use of a certain interval graph naturally associated with the problem instance and a simple dynamic program on this interval graph. The linear dependency on n is also achieved through the use of this interval graph. © 2012 Springer-Verlag.
  • 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年 [査読有り][通常論文]
     
    We give an algorithm for computing the directed pathwidth of a digraph with n vertices in O(1.89n) time. This is the first algorithm with running time better than the straightforward O*(2n). As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in O(1.9657n) time. © 2012 Springer-Verlag.
  • 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年 [査読有り][通常論文]
     
    An orientation of an undirected graph G is a directed graph D on V(G) with exactly one of directed edges (u, v) and (v, u) for each pair of vertices u and v adjacent in 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. © 2010 Springer-Verlag.

MISC

  • 藤原 優, 吉岡 和希, 小林 靖明 人工知能学会研究会資料 人工知能基本問題研究会 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月
  • 志田祐仁, 有村博紀, 小林靖明 電子情報通信学会技術研究報告(Web) 123 (325(COMP2023 16-27)) 2023年
  • 舟山諒, 小林靖明 電子情報通信学会技術研究報告(Web) 123 (325(COMP2023 16-27)) 2023年
  • HANAKA Tesshu, KOBAYASHI Yasuaki, KURITA Kazuhiro 情報処理学会研究報告(Web) 2023 (AL-192) 2023年
  • 小林靖明, 栗田和宏, 和佐州洋 日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集 2023 2023年
  • 佐藤嶺, 小林靖明, 栗田和宏, 和佐州洋 電子情報通信学会技術研究報告(Web) 123 (325(COMP2023 16-27)) 2023年
  • Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki CoRR abs/2305.07262 2023年
  • 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年
  • 須江瑞樹, 小林靖明, 有村博紀, 中島祐人, 稲永俊介 電子情報通信学会技術研究報告(Web) 122 (294(COMP2022 21-32)) 2022年
  • 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日
  • 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.
  • 小林 靖明, 栗田 和宏 人工知能学会研究会資料 人工知能基本問題研究会 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.
  • 小林 靖明 人工知能 36 (3) 328 -328 2021年05月01日
  • 小林靖明 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つ目のアルゴリズムは全ての極大マッチングを要素数が非増加の順序で列挙するアルゴリズムであり，これも多項式遅延で動作する．
  • Hikaru Shindo, Masaaki Nishino, Yasuaki Kobayashi, Akihiro Yamamoto CoRR abs/2003.03960 2020年
  • Yasuaki Kobayashi, Yota Otachi CoRR abs/2007.08811 2020年
  • 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年
  • 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.
  • 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.
  • 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年 [査読無し][通常論文]
  • 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年
  • 新藤光, 西野正彬, 小林靖明, 山本章博 人工知能学会人工知能基本問題研究会資料 110th 03 2019年
  • 小林靖明, 曽根大雅, 土中哲秀 電子情報通信学会技術研究報告 119 (314(MSS2019 23-40)) 41 -46 2019年 [査読無し][通常論文]
  • 小林靖明, 中畑裕 人工知能学会人工知能基本問題研究会資料 110th 19 -24 2019年 [査読無し][通常論文]
  • 里見琢聞, 小林靖明, 山本章博 人工知能学会人工知能基本問題研究会資料 109th 78 -82 2019年 [査読無し][通常論文]
  • 久保田稜, 小林靖明, 山本章博 人工知能学会人工知能基本問題研究会資料 108th 39 -44 2019年 [査読無し][通常論文]
  • 小林靖明 電子情報通信学会技術研究報告 118 (216(COMP2018 9-20)(Web)) 2018年
  • 向井達郎, 小林靖明, 紫藤佑介, 山本章博, 宮本篤志, 松村忠幸, 嶺竜治 情報処理学会研究報告(Web) 2018 (SE-199) 2018年
  • 久保田稜, 小林靖明, 山本章博 人工知能学会人工知能基本問題研究会資料 106th 82 -87 2018年 [査読無し][通常論文]
  • 紫藤 佑介, 山本 章博, 小林 靖明, 久保山 哲二 人工知能基本問題研究会 103 89 -94 2017年03月13日 [査読無し][通常論文]
  • 山浦 智佳子, 小林 靖明, 山本 章博, 久保山 哲二 人工知能基本問題研究会 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) である.
  • 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.
  • 大野 志郎, 横山 悦郎, 城所 弘泰, 伊藤 大河, 小林 靖明 学習院大学計算機センター年報 36 (36) 81 -88 2015年01月01日 [査読無し][通常論文]
  • 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.
  • 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.
  • 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^+n^ time which improves on the previously best known algorithm with running time 2^n.
  • 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.
  • 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.

共同研究・競争的資金等の研究課題

  • 日本学術振興会：科学研究費助成事業 基盤研究(B)
    研究期間 : 2023年04月 -2028年03月 
    代表者 : 小林 靖明
  • 日本学術振興会：科学研究費助成事業 基盤研究(A)
    研究期間 : 2020年04月 -2025年03月 
    代表者 : 有村 博紀, 宇野 毅明, 平田 耕一, 山本 章博, 喜田 拓也, ジョーダン チャールズハロルド, 小林 靖明
  • 日本学術振興会：科学研究費助成事業
    研究期間 : 2021年04月 -2024年03月 
    代表者 : 山本 章博, 小林 靖明
  • 日本学術振興会：科学研究費助成事業 学術変革領域研究(B)
    研究期間 : 2020年10月 -2023年03月 
    代表者 : 伊藤 健洋, 大舘 陽太, 小林 靖明, 和佐 州洋
     
    2020年10月の交付内定からすぐにオンラインでの研究打合せを開始し，本計画研究班の研究目的を改めて研究分担者らと共有した．また，2020年11月と12月には，対面を含む打合せも開催した．そして，具体的に取り組むべき研究として，まずはMouawadらが与えた単項二階述語論理を用いたメタ定理を精査した．このメタ定理は，Courcelleが1990年に組合せ遷移問題ではない問題に対して開発したメタ定理を基にしており，組合せ遷移問題に特有の遷移系列をどのように扱うことで，Mouawadらがメタ定理を開発したのかを重点的に解析した．その結果，遷移系列の長さをパラメータとしている点が，Mouawadらのメタ定理では非常に強く作用していることが判明した．これは，ある意味で，扱う問題の遷移系列の長さに制限があるといえる．そこで本計画研究班では，この遷移系列の長さをパラメータから外すことができないかを議論し，その検討を進めている． また，C01班との連携も開始しており，特に「非対称的な遷移」に関するアルゴリズム研究に力を入れた．これまで研究されてきた組合せ遷移問題のほとんどは，対称的な遷移を扱っており，非対称的な遷移は従来研究の一般化となっている．我々は，具体的には，有向グラフにおける独立集合の遷移問題に取り組み，その計算困難性と容易性について解析を進めた． この他にも，列挙アルゴリズムや指数時間アルゴリズムなど，近接分野の代表的なアルゴリズム手法を組合せ遷移問題へ適用できないか考察を行った．
  • 日本学術振興会：科学研究費助成事業 若手研究
    研究期間 : 2020年04月 -2023年03月 
    代表者 : 小林 靖明
     
    本研究の目的であるグラフの幅パラメータを用いたアルゴリズム的メタ定理に向けての研究を行った．具体的には，グラフの幅パラメータとして最も成功している，木幅をより制限することにより，様々な問題の固定パラメータ容易性を示した．これらは，グラフの木幅をパラメータとしてもW[1]困難性を示すことができ，既存のメタ定理を用いて解くことができない問題群であり，それらを解くための新たなメタ定理の表現方法に関して知見を得ることができた． また，既存のメタ定理で扱っているような最適化問題やモデル検査問題だけでなく，列挙問題や組合せ遷移問題に対してメタ定理の可能性を検討した．この過程において，既存の疎グラフに対するアルゴリズム的メタ定理の既存の方法を包括的にサーベイし，列挙問題や組合せ遷移問題に対するアルゴリズム的メタ定理への知見やその実現可能性を得ることができた． 本研究テーマから得た知見を生かして，人工知能分野で研究される問題についても取り組んだ．具体的には最適化問題の解の多様性の研究にも取り組んだ．これらの問題は古典的な最適化問題の一般化になっており，応用の観点と計算量理論の観点でいずれも興味深く，これらの問題に集中的に取り組みいくつかの結果を得て国内外の会議で発表を行った．
  • 日本学術振興会：科学研究費助成事業 基盤研究(B)
    研究期間 : 2017年04月 -2020年03月 
    代表者 : 山本 章博, 小林 靖明, 久保山 哲二
     
    本研究は,自然言語データにおける本文とキーワードの関係，Webページ間のリンク構造における参照元と参照先の関係など，２つの離散値属性間の２項関係から部分関係を抽出することによる知識発見を対象とする．研究計画で設定した[課題１]～[課題５]のうち，本年度は，[課題１]閉集合が数学的に定義されているためノイズを許さないため実用に向かないことがある一方，密集合は実応用から提案されたためノイズを許容するものの数学的な定義がない，という相補的な点に着目し，密な部分関係を弱閉集合として集合論的に定式化する[課題３]の弱集合に対して，閉集合と同様の不動点意味論を構成する，[課題５]弱集合の効率的列挙アルゴリズムの開発と実用性検討，の３課題を中心に研究を展開したした． [課題１]については，閉集合をグラフ理論のことばを用いれば，２部グラフの完全部分グラフという解釈が可能であることに着目し，グラフ理論における完全グラフの定義を弱めたk-Plexという概念を範として，弱集合を(k,l)-閉集合として定式化した．以下では弱集合を(k,l)-閉集合とよぶ． そして，[課題３]の不動点を構成するための反復関数を，オリジナルの閉集合のための反復関数を修正して定式化した上で，(k,l)-閉集合と反復関数の不動点の関係を与えた．閉集合の場合は，反復関数の不動点と閉集合は１対１に対応するが，(k,l)-閉集合の場合は必ずしも１対１にはならないこと，そもそも反復関数が収束しないことがあることも示した．これらの結果をもとに，[課題５]に取り組み，閉集合の高速列挙アルゴリズムであるLCMを修正することにより，(k,l)-閉集合の列挙が可能であることを示した．このアルゴリズムは，理論上は高速な列挙が不可能な場合もあるが，現実の小規模データに対しては十分高速に列挙することを確認した．
  • 日本学術振興会：科学研究費助成事業 基盤研究(B)
    研究期間 : 2014年04月 -2017年03月 
    代表者 : 山本 章博, 平田 耕一, 伊藤 公人, 久保山 哲二, 吉仲 亮, 小林 靖明, 池田 真土里, 大滝 啓介, 狩山 和亮, 山崎 朋哉, 西村 翔一
     
    本研究の目標は，属性が備える順序関係と閉集合を利用した知識発見手法を開発することであった．閉集合による知識発見は２項関係データの双クラスタリングとよばれる手法の一種であるので，行列の因子分解と探索による閉集合構成，様々な双クラスタリング手法で得られた閉集合間の関係解析を行った．また，木構造データの部分構造間の半順序を用いた木構造の主成分分析手法，自然言語シソーラスにおける語彙の順序関係を用いたシソーラス拡張，整数計画法による木構造の共通部分の高速発見手法という成果を得た．
  • 日本学術振興会：科学研究費助成事業 研究活動スタート支援
    研究期間 : 2014年08月 -2016年03月 
    代表者 : 小林 靖明
     
    本研究ではグラフの階層描画の手法として知られるSugiyama methodに対して厳密アルゴリズムの適用を行った．Sugiyama methodに関してはいくつかのヒューリスティックアルゴリズムを用いた方法が知られているが，厳密アルゴリズムを適用する研究は知られていない．本研究の実験において，交差数を最小化する固定パラメータアルゴリズムが十分に有用であることを明らかにした．また，階層を2層に限定した場合について既存のアルゴリズムよりも高速なアルゴリズムの開発に成功した．

Copyright © MEDIA FUSION Co.,Ltd. All rights reserved.