MF研究者総覧

Researcher Database

Advance
Researchers' Page on researchmap
Last Updated :2024/08/24

Researcher Profile and Settings

Master

Affiliation (Master)

  • Faculty of Information Science and Technology　Computer Science and Information Technology　Knowledge Software Science

Affiliation (Master)

  • Faculty of Information Science and Technology　Computer Science and Information Technology　Knowledge Software Science

researchmap

Profile and Settings

Affiliation

  • Hokkaido University

Profile and Settings

  • Name (Japanese)

    Kobayashi

  • Name (Kana)

    Yasuaki

  • Name

    201601002248769544

Affiliation

  • Hokkaido University

Achievement

Research Areas

  • Informatics / Mathematical informatics
  • Informatics / Intelligent informatics
  • Informatics / Information theory

Awards

  • 2024 WALCOM 2024 Best Paper Award
  • 2021 人工知能学会 研究会優秀賞
  • 2019 IWOCA 2019 Best Paper Award
  • 2017 The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge Track B, 1st place
  • 2014 情報処理学会 コンピューターサイエンス領域奨励賞
  • 2012 日本オペレーションズ・リサーチ学会 「OR横断若手の会研究部会」 学生優秀発表賞

Published Papers

  • AOIKE Yuuki, KIYOMI Masashi, KOBAYASHI Yasuaki, OTACHI Yota
    IEICE Transactions on Information and Systems E107.D (4) 559 - 563 0916-8532 2024/04/01 [Refereed][Not invited]
     
    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 [Refereed]
  • 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 [Refereed]
  • 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 [Refereed]
  • Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou
    Proceedings of WALCOM 2024 421 - 435 2024 [Refereed]
  • Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otachi
    WALCOM2024, LNCS 14549 406 - 420 2024 [Refereed]
  • 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 [Refereed]
  • Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
    Proceedings of MFCS 2023, LIPIcs (58) 1 - 14 2023 [Refereed]
  • Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki
    Proceedings of WADS 2023, LNCS 14079 521 - 532 2023 [Refereed]
  • Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi
    Proceedings of AAAI 2023 3968 - 3976 2023 [Refereed]
  • Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa
    Theoretical Computer Science 943 131 - 141 0304-3975 2022/12 [Refereed]
  • Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota Otachi
    Proceedings of the AAAI Conference on Artificial Intelligence 36 (4) 3758 - 3766 2159-5399 2022/06/28 [Refereed]
     
    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 [Refereed]
  • Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
    Proceedings of WG 2022, LNCS 13453 342 - 355 2022 [Refereed]
  • Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi
    Proceedings of ESA 2022, LIPIcs 244 (61) 1 - 15 2022 [Refereed]
  • Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa
    Proceedings of MFCS 2022, LIPIcs 241 (58) 1 - 15 2022 [Refereed]
  • Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, Saket Saurabh
    Proceedings of MFCS 2022, LIPIcs 241 (6) 1 - 15 2022 [Refereed]
  • Yasuaki Kobayashi, Yota Otachi
    Algorithmica 84 (8) 2379 - 2393 2022 [Refereed]
  • Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi
    Theor. Comput. Sci. 918 60 - 76 2022 [Refereed]
  • Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi
    Theory Comput. Syst. 66 (2) 502 - 515 2022 [Refereed]
  • Yasuaki Kobayashi, Shin-ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka
    IEICE Trans. Inf. Syst. 105 (3) 503 - 507 2022 [Refereed]
  • 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 [Refereed]
  • Eto, H., Ito, T., Kobayashi, Y., Otachi, Y., Wasa, K.
    Proceedings of WALCOM 2022 13174 LNCS 35 - 46 1611-3349 2022 [Refereed]
  • Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa
    Proceedings of COCOON 2021, LNCS 13025 343 - 354 2021 [Refereed]
  • Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
    Theor. Comput. Sci. 873 38 - 46 2021 [Refereed]
  • Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi
    Proceedings of CIAC 2021, LNCS 12701 271 - 285 2021 [Refereed]
     
    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 [Refereed][Not invited]
     
    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 [Refereed][Not invited]
     
    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 [Refereed][Not invited]
     
    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 1611-3349 2021 [Refereed]
     
    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 [Refereed]
  • Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
    Proceedings of FAW 2020, LNCS 12340 25 - 36 2020/11 [Refereed][Not invited]
     
    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 0302-9743 2020/08/08 [Refereed][Not invited]
     
    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 [Refereed][Not invited]
  • Kazuhiro Kurita, Yasuaki Kobayashi
    Proceedings of MFCS 2020 60:1 - 60:14 2020/08 [Refereed][Not invited]
     
    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 0178-4617 2020 [Refereed][Not invited]
  • Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi
    Leibniz International Proceedings in Informatics, LIPIcs 148 13:1 - 13:15 1868-8969 2019/12 [Refereed][Not invited]
     
    © 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 1868-8969 2019/12 [Refereed][Not invited]
     
    © 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 [Refereed][Not invited]
     
    © 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 0302-9743 2019 [Refereed][Not invited]
     
    © 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 0302-9743 2019 [Refereed][Not invited]
     
    © 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 1868-8969 2018/02/01 [Refereed][Not invited]
     
    © 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 1868-8969 2017/02/01 [Refereed][Not invited]
     
    © 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 0302-9743 2017 [Refereed][Not invited]
     
    © 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 0020-0190 2016/09/01 [Refereed][Not invited]
     
    © 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 0178-4617 2016/05/01 [Refereed][Not invited]
     
    © 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 0178-4617 2015/07/12 [Refereed][Not invited]
     
    © 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 0020-0190 2015/02 [Refereed][Not invited]
     
    © 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 0302-9743 2015 [Refereed][Not invited]
     
    © 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 0304-3975 2014 [Refereed][Not invited]
     
    © 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 0302-9743 2014 [Refereed][Not invited]
     
    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 0302-9743 2013 [Refereed][Not invited]
     
    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 0302-9743 2012 [Refereed][Not invited]
     
    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 0302-9743 2012 [Refereed][Not invited]
     
    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 0302-9743 2010 [Refereed][Not invited]
     
    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
  • KOBAYASHI Yasuaki, KOBAYASHI Yusuke, OTACHI Yota  JSAI Technical Report, SIG-FPAI  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.
  • KOBAYASHI Yasuaki, KURITA Kazuhiro  JSAI Technical Report, SIG-FPAI  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
  • Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa  CoRR  abs/2105.04146-  2E1OS13a03  -2E1OS13a03  2021  
    We present polynomial-delay enumeration algorithms for maximal matchings with cardinality at least given threshold t. The first algorithm enumerates all such matchings in O(m2) delay, where m is the number of edges of an input graph. This extends known results for enumerating maximal matchings to the cardinality constrained problem. The second algorithm enumerates all maximal matchings in non-ascending order of its cardinality and runs in polynomial delay.
  • 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  [Not refereed][Not invited]
     
    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  [Not refereed][Not invited]
     
    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  [Not refereed][Not invited]
     
    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  [Not refereed][Not invited]
  • Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki  arXiv  2019/04/10  [Not refereed][Not invited]
     
    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
  • SHINDO Hikaru, NISHINO Masaaki, KOBAYASHI Yasuaki, YAMAMOTO Akihiro  JSAI Technical Report, SIG-FPAI  110th-  03  2019
  • 小林靖明, 曽根大雅, 土中哲秀  電子情報通信学会技術研究報告  119-  (314(MSS2019 23-40))  41  -46  2019  [Not refereed][Not invited]
  • 小林靖明, 中畑裕  人工知能学会人工知能基本問題研究会資料  110th-  19  -24  2019  [Not refereed][Not invited]
  • SATOMI Takumon, KOBAYASHI Yasuaki, YAMAMOTO Akihiro  JSAI Technical Report, SIG-FPAI  109th-  78  -82  2019  [Not refereed][Not invited]
  • KUBOTA Ryo, KOBAYASHI Yasuaki, YAMAMOTO Akihiro  JSAI Technical Report, SIG-FPAI  108th-  39  -44  2019  [Not refereed][Not invited]
  • 小林靖明  電子情報通信学会技術研究報告  118-  (216(COMP2018 9-20)(Web))  2018
  • 向井達郎, 小林靖明, 紫藤佑介, 山本章博, 宮本篤志, 松村忠幸, 嶺竜治  情報処理学会研究報告(Web)  2018-  (SE-199)  2018
  • KUBOTA Ryo, KOBAYASHI Yasuaki, YAMAMOTO Akihiro  JSAI Technical Report, SIG-FPAI  106th-  82  -87  2018  [Not refereed][Not invited]
  • SHIDO Yusuke, YAMAMOTO Akihiro, KOBAYASHI Yasuaki, KUBOYAMA Tetsuji  JSAI Technical Report, SIG-FPAI  103-  89  -94  2017/03/13  [Not refereed][Not invited]
  • YAMAURA Chikako, KOBAYASHI Yasuaki, YAMAMOTO Akihiro, KUBOYAMA Tetsuji  JSAI Technical Report, SIG-FPAI  103-  67  -72  2017/03/13  [Not refereed][Not invited]
  • 小林靖明  学習院大学計算機センター年報  37-  2017
  • 大塚広夢, 小林靖明, 玉木久夫  情報処理学会研究報告(Web)  2017-  (AL-161)  2017
  • 小林靖明, 玉木久夫  情報処理学会研究報告(Web)  2017-  (AL-164)  2017
  • HONG Eunpyeong, 小林靖明, 山本章博  人工知能学会人工知能基本問題研究会資料  103rd-  78  -83  2017  [Not refereed][Not invited]
  • 小林 靖明, 玉木 久夫  電子情報通信学会技術研究報告 = IEICE technical report : 信学技報  115-  (316)  53  -58  2015/11/20  [Not refereed][Not invited]
  • 橘内 謙太, 小林 靖明, 玉木 久夫  情報処理学会研究報告. AL, アルゴリズム研究会報告  2015-  (3)  1  -8  2015/02/24  [Not refereed][Not invited]
     
    有向グラフ 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  IPSJ SIG Notes  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.
  • 大野 志郎, 横山 悦郎, 城所 弘泰, 伊藤 大河, 小林 靖明  学習院大学計算機センター年報  36-  (36)  81  -88  2015/01/01  [Not refereed][Not invited]
  • Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki  IPSJ SIG Notes  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.
  • Yasuaki Kobayashi  IPSJ SIG Notes  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.
  • KOBAYASHI YASUAKI, MARUTA HIROKAZU, NAKAE YUSUKE, TAMAKI HISAO  IEICE technical report. Theoretical foundations of Computing  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  IPSJ SIG Notes  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.
  • 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.

Research Projects

  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2024/04 -2028/03 
    Author : 玉木 久夫, 齋藤 寿樹, 大舘 陽太, 川原 純, 吉仲 亮, 小林 靖明
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2024/04 -2028/03 
    Author : 伊藤 健洋, 宋 剛秀, 小林 靖明, 野崎 雄太
  • 日本学術振興会：科学研究費助成事業 基盤研究(B)
    Date (from‐to) : 2023/04 -2028/03 
    Author : 小林 靖明
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
    Date (from‐to) : 2020/04 -2025/03 
    Author : 有村 博紀, 宇野 毅明, 平田 耕一, 山本 章博, 喜田 拓也, ジョーダン チャールズハロルド, 小林 靖明
  • 日本学術振興会：科学研究費助成事業
    Date (from‐to) : 2021/04 -2024/03 
    Author : 山本 章博, 小林 靖明
  • 日本学術振興会：科学研究費助成事業 学術変革領域研究(B)
    Date (from‐to) : 2020/10 -2023/03 
    Author : 伊藤 健洋, 大舘 陽太, 小林 靖明, 和佐 州洋
     
    2020年10月の交付内定からすぐにオンラインでの研究打合せを開始し，本計画研究班の研究目的を改めて研究分担者らと共有した．また，2020年11月と12月には，対面を含む打合せも開催した．そして，具体的に取り組むべき研究として，まずはMouawadらが与えた単項二階述語論理を用いたメタ定理を精査した．このメタ定理は，Courcelleが1990年に組合せ遷移問題ではない問題に対して開発したメタ定理を基にしており，組合せ遷移問題に特有の遷移系列をどのように扱うことで，Mouawadらがメタ定理を開発したのかを重点的に解析した．その結果，遷移系列の長さをパラメータとしている点が，Mouawadらのメタ定理では非常に強く作用していることが判明した．これは，ある意味で，扱う問題の遷移系列の長さに制限があるといえる．そこで本計画研究班では，この遷移系列の長さをパラメータから外すことができないかを議論し，その検討を進めている． また，C01班との連携も開始しており，特に「非対称的な遷移」に関するアルゴリズム研究に力を入れた．これまで研究されてきた組合せ遷移問題のほとんどは，対称的な遷移を扱っており，非対称的な遷移は従来研究の一般化となっている．我々は，具体的には，有向グラフにおける独立集合の遷移問題に取り組み，その計算困難性と容易性について解析を進めた． この他にも，列挙アルゴリズムや指数時間アルゴリズムなど，近接分野の代表的なアルゴリズム手法を組合せ遷移問題へ適用できないか考察を行った．
  • 日本学術振興会：科学研究費助成事業 若手研究
    Date (from‐to) : 2020/04 -2023/03 
    Author : 小林 靖明
     
    本研究の目的であるグラフの幅パラメータを用いたアルゴリズム的メタ定理に向けての研究を行った．具体的には，グラフの幅パラメータとして最も成功している，木幅をより制限することにより，様々な問題の固定パラメータ容易性を示した．これらは，グラフの木幅をパラメータとしてもW[1]困難性を示すことができ，既存のメタ定理を用いて解くことができない問題群であり，それらを解くための新たなメタ定理の表現方法に関して知見を得ることができた． また，既存のメタ定理で扱っているような最適化問題やモデル検査問題だけでなく，列挙問題や組合せ遷移問題に対してメタ定理の可能性を検討した．この過程において，既存の疎グラフに対するアルゴリズム的メタ定理の既存の方法を包括的にサーベイし，列挙問題や組合せ遷移問題に対するアルゴリズム的メタ定理への知見やその実現可能性を得ることができた． 本研究テーマから得た知見を生かして，人工知能分野で研究される問題についても取り組んだ．具体的には最適化問題の解の多様性の研究にも取り組んだ．これらの問題は古典的な最適化問題の一般化になっており，応用の観点と計算量理論の観点でいずれも興味深く，これらの問題に集中的に取り組みいくつかの結果を得て国内外の会議で発表を行った．
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research
    Date (from‐to) : 2017/04 -2020/03 
    Author : Yamamoto Akihiro
     
    In this research, in order to admit noise in closed sets in a binary relation between two discrete-valued attributes, we formulated weakly closed sets using set theory and constructed an algorithm for enumerating weakly closed sets. We defined weakly closed sets based on the fact that closed sets can be interpreted using graphs. We designed an algorithm for enumerating weakly closed sets with modifying the well-known fast enumeration algorithm for closed sets. Furthermore, by modifying the definition of weakly closed sets and the enumeration algorithm to the trajectory data collected from travelers, we succeeded in enumerating the routes frequently followed by them as weakly closed sets. We also showed that the fixpoint semantics of closed sets cannot be given to weakly closed sets in general.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
    Date (from‐to) : 2014/04 -2017/03 
    Author : Yamamoto Akihiro, AVIS David, KOBAYASHI Yasuaki, IKEDA Madori, OTAKI Keisuke, KARIYAMA Kazuaki, YAMAZAKI Tomoya, NISHIMURA Shoichi
     
    The goal of this research is to develop methods for knowledge discovery that uses both orders for attribute values and closed sets of from mixed data. Since knowledge discovery by closed set is one kind of technique called bi-clustering of binary relational data, we obtained a method for bi-clustering for matrix factorization and search of matrices. Also we analyzed relationship between closed sets obtained by various bi-clustering method. Moreover, we developed methods for principal component analysis of the tree structure using the partial order of the substructure of tree data, the thesaurus expansion using the order relation of the vocabulary in the natural language thesaurus, and discovery methods of the similarity of the tree structure data with the integer programming.
  • Japan Society for the Promotion of Science：Grants-in-Aid for Scientific Research Grant-in-Aid for Research Activity start-up
    Date (from‐to) : 2014/08 -2016/03 
    Author : Yasuaki Kobayashi
     
    In this research, we apply exact algorithms to a well-known layered graph drawing technique, called Sugiyama method. Although several heuristic approaches are known for this method, no exact approach is known in the literature. Our experimental study shows that the state-of-the-art fixed parameter algorithm for minimizing the number of crossings is substantially applicable to reasonable-sized instances.Moreover, we give a new fixed parameter algorithm for the two-layer case, which improves the running time of the previously known fixed parameter algorithm.

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