Updated on 2022/03/28

写真a

 
OTACHI Yota
 
Organization
Graduate School of Informatics Department of Mathematical Informatics 2 Associate professor
Graduate School
Graduate School of Informatics
Undergraduate School
School of Informatics Department of Natural Science Informatics
Title
Associate professor

Degree 1

  1. 博士(工学) ( 2010.3   群馬大学 ) 

Research Interests 2

  1. グラフアルゴリズム

  2. アルゴリズム

Research Areas 2

  1. Informatics / Mathematical informatics

  2. Informatics / Theory of informatics

Research History 4

  1. Nagoya University   Department of Mathematical Informatics, Graduate School of Informatics   Associate professor

    2020.3

      More details

    Country:Japan

  2. Kumamoto University   Faculty of Advanced Science and Technology   Associate professor

    2017.5 - 2020.2

  3. Japan Advanced Institute of Science and Technology   School of Information Science   Assistant Professor

    2012.4 - 2017.4

  4. Tohoku University   Graduate School of Information Sciences   Assistant Professor

    2011.4 - 2012.3

Education 3

  1. Gunma University   Graduate School, Division of Engineering

    - 2010.3

      More details

    Country: Japan

  2. Gunma University   Graduate School, Division of Engineering

    - 2007.3

      More details

    Country: Japan

  3. Gunma University   Faculty of Engineering

    - 2005.3

      More details

    Country: Japan

Awards 6

  1. Incentive Award

    2021.6   JSAI   Algorithms for Finding Diverse Subgraphs

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi

  2. 山下記念研究賞

    2019.3   情報処理学会  

     More details

    Award type:Award from Japanese society, conference, symposium, etc.  Country:Japan

  3. LA/EATCS-Japan発表論文賞

    2018.2   LAシンポジウム/EATCS Japan Chapter  

     More details

    Award type:Award from Japanese society, conference, symposium, etc.  Country:Japan

  4. LA/EATCS-Japan発表論文賞

    2017.2   LAシンポジウム/EATCS Japan Chapter  

     More details

    Award type:Award from Japanese society, conference, symposium, etc.  Country:Japan

  5. 北陸先端科学技術大学院大学 学長賞(研究活動賞)

    2015.10   北陸先端科学技術大学院大学  

     More details

    Country:Japan

  6. コンピュータサイエンス領域奨励賞

    2011.9   情報処理学会  

     More details

    Award type:Award from Japanese society, conference, symposium, etc.  Country:Japan

▼display all

 

Papers 116

  1. Finding diverse trees, paths, and more Reviewed

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi

    AAAI 2021: Proceedings of the 35th AAAI Conference on Artificial Intelligence     2021.2

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

  2. Token Sliding on Split Graphs. Reviewed

    Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora

    Theory of Computing Systems   Vol. 65 ( 4 ) page: 662 - 686   2021

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1007/s00224-020-09967-8

  3. Reconfiguring Directed Trees in a Digraph. Reviewed

    Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa

    Computing and Combinatorics - 27th International Conference(COCOON)     page: 343 - 354   2021

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

    DOI: 10.1007/978-3-030-89543-3_29

    Other Link: https://dblp.uni-trier.de/db/conf/cocoon/cocoon2021.html#ItoIKNOW21

  4. On the security number of the Cartesian product of graphs. Reviewed

    Marko Jakovac, Yota Otachi

    Discrete Applied Mathematics   Vol. 304   page: 119 - 128   2021

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1016/j.dam.2021.07.030

  5. Low-congestion shortcut and graph parameters. Reviewed

    Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi

    Distributed Computing   Vol. 34 ( 5 ) page: 349 - 365   2021

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1007/s00446-021-00401-x

  6. Longest common subsequence in sublinear space. Reviewed

    Masashi Kiyomi, Takashi Horiyama, Yota Otachi

    Information Processing Letters   Vol. 168   page: 106084 - 106084   2021

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1016/j.ipl.2020.106084

  7. Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity. Reviewed

    Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi

    Algorithms and Complexity - 12th International Conference(CIAC)     page: 271 - 285   2021

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

    DOI: 10.1007/978-3-030-75242-2_19

    Other Link: https://dblp.uni-trier.de/db/conf/ciac/ciac2021.html#GimaHKKO21

  8. Distributed Reconfiguration of Spanning Trees. Reviewed

    Yukiko Yamauchi, Naoyuki Kamiyama, Yota Otachi

    Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium(SSS)     page: 516 - 520   2021

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

    DOI: 10.1007/978-3-030-91081-5_40

    Other Link: https://dblp.uni-trier.de/db/conf/sss/sss2021.html#YamauchiKO21

  9. Computational Complexity of Jumping Block Puzzles. Reviewed

    Masaaki Kanzaki, Yota Otachi, Ryuhei Uehara

    Computing and Combinatorics - 27th International Conference(COCOON)     page: 655 - 667   2021

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

    DOI: 10.1007/978-3-030-89543-3_54

    Other Link: https://dblp.uni-trier.de/db/conf/cocoon/cocoon2021.html#KanzakiOU21

  10. Subgraph isomorphism on graph classes that exclude a substructure Reviewed International coauthorship

    Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Tom van der Zanden

    Algorithmica   Vol. 82   page: 3566-3587   2020.12

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1007/s00453-020-00737-z

  11. Parameterized complexity of graph burning Reviewed

    Yasuaki Kobayashi, Yota Otachi

    Leibniz International Proceedings in Informatics   Vol. 180   page: 21:1-21:10   2020.12

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.IPEC.2020.21

  12. Linear-time recognition of double-threshold graphs Reviewed

    Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno

    Lecture Notes in Computer Science   Vol. 12301   page: 286-297   2020.10

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.1007/978-3-030-60440-0_23

  13. Symmetric assembly puzzles are hard, beyond a few pieces Reviewed International coauthorship

    Erik D. Demaine, Matias Korman, Jason S. Ku, Joseph S.B. Mitchell, Yota Otachi, André van Renssen, Marcel Roeloffzen, Ryuhei Uehara, Yushi Uno

    Computational Geometry: Theory and Applications   Vol. 90   page: Article 101648   2020.10

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1016/j.comgeo.2020.101648

  14. Independent set reconfiguration parameterized by modular-width Reviewed International coauthorship

    Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi

    Algorithmica   Vol. 82   page: 2586-2605   2020.9

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1007/s00453-020-00700-y

  15. Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs Reviewed

    Taisuke Izumi, Yota Otachi

    Leibniz International Proceedings in Informatics   Vol. 168   page: 67:1-67:17   2020.7

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.ICALP.2020.67

  16. Parameterized Orientable Deletion Reviewed International coauthorship

    Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora

    Algorithmica   Vol. 82   page: 1909-1938   2020.7

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1007/s00453-020-00679-6

  17. Parameterized Complexity of $$(A,\ell )$$-Path Packing Reviewed International coauthorship

    Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

    Lecture Notes in Computer Science   Vol. 12126   page: 43 - 55   2020.6

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Part of collection (book)   Publisher:Springer International Publishing  

    DOI: 10.1007/978-3-030-48966-3_4

  18. Hedonic seat arrangement problems (Extended abstract) Reviewed International coauthorship

    Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

    AAMAS 2020: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems     page: 1777-1779   2020.5

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

  19. Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph Reviewed International coauthorship

    Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, Kunihiro Wasa

    Theoretical Computer Science   Vol. 818   page: 2-11   2020.5

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1016/j.tcs.2018.08.009

  20. Space-efficient algorithms for longest increasing subsequence Reviewed International coauthorship

    Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui

    Theory of Computing Systems   Vol. 64   page: 522-541   2020.4

     More details

    Authorship:Corresponding author   Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1007/s00224-018-09908-6

  21. Parameterized complexity of safe set Reviewed International coauthorship

    Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi

    Journal of Graph Algorithms and Applications   Vol. 24   page: 215-245   2020.4

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.7155/jgaa.00528

  22. Grundy Distinguishes Treewidth from Pathwidth. Reviewed International coauthorship

    Rémy Belmonte, Eun Jung Kim 0002, Michael Lampis, Valia Mitsou, Yota Otachi

    28th Annual European Symposium on Algorithms(ESA)   Vol. 173   page: 14 - 19   2020

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

    DOI: 10.4230/LIPIcs.ESA.2020.14

    Other Link: https://dblp.uni-trier.de/db/conf/esa/esa2020.html#Belmonte0LMO20

  23. K3 Edge Cover Problem in a Wide Sense. Reviewed International coauthorship

    Kyohei Chiba, Rémy Belmonte, Hiro Ito, Michael Lampis, Atsuki Nagao, Yota Otachi

    Journal of Information Processing   Vol. 28 ( 0 ) page: 849 - 858   2020

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.2197/ipsjjip.28.849

  24. Hedonic Seat Arrangement Problems. Reviewed

    Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

    Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems(AAMAS)     page: 1777 - 1779   2020

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:International Foundation for Autonomous Agents and Multiagent Systems  

    Other Link: https://dblp.uni-trier.de/conf/atal/2020

  25. A Survey on Spanning Tree Congestion.

    Yota Otachi

    Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday     page: 165 - 172   2020

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

    DOI: 10.1007/978-3-030-42071-0_12

    Other Link: https://dblp.uni-trier.de/db/conf/birthday/bodlaender2020.html#Otachi20

  26. Combined graph kernels for automatic patent classification: A hybrid approach Reviewed

    Budi Nugroho, Masayoshi Aritsugi, Yota Otachi, Yuki Manabe

    World Patent Information   Vol. 57   page: 18 - 24   2019.6

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    © 2019 Elsevier Ltd In this study, we proposed combined kernel-based methods to leverage patent citation graph performance for patent classification. The concept is to use the combined graph kernels of the citation graph to classify patent documents, as a hybrid approach. A multiple kernel framework was used for integrating multiple datasets of various kernels into a combined kernel. We employed seven graph kernels as the baselines and the combination of random walks and Weisfeiler–Lehman subtree kernels to achieve higher performance. We calculated the kernel values of each patent pairwise and employed an SVM classifier to carry out the classification task. The investigation results demonstrate that the combined graph kernel outperforms single kernels.

    DOI: 10.1016/j.wpi.2019.03.002

    Scopus

  27. Subgraph Isomorphism on Graph Classes that Exclude a Substructure. Reviewed International coauthorship

    Hans L. Bodlaender, Tesshu Hanaka, Yoshio Okamoto, Yota Otachi, Tom C. van, der Zanden

    Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings   Vol. 11485   page: 87 - 98   2019

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:Springer  

    DOI: 10.1007/978-3-030-17402-6_8

  28. Independent Set Reconfiguration Parameterized by Modular-Width. Reviewed International coauthorship

    Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi

    Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers   Vol. 11789   page: 285 - 297   2019

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:Springer  

    DOI: 10.1007/978-3-030-30786-8_22

  29. Low-Congestion Shortcut and Graph Parameters. Reviewed

    Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi

    Leibniz International Proceedings in Informatics   Vol. 146   page: 25:1-25:17   2019

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.DISC.2019.25

  30. Parameterized Complexity of Safe Set. Reviewed International coauthorship

    Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi

    Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings   Vol. 11485   page: 38 - 49   2019

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:Springer  

    DOI: 10.1007/978-3-030-17402-6_4

  31. How Bad is the Freedom to Flood-It? Reviewed International coauthorship

    Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi

    J. Graph Algorithms Appl.   Vol. 23 ( 2 ) page: 111 - 134   2019

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.7155/jgaa.00486

  32. A lower bound on opaque sets. Reviewed International coauthorship

    Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, János Pach

    Comput. Geom.   Vol. 80   page: 13 - 22   2019

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1016/j.comgeo.2019.01.002

  33. On the Classes of Interval Graphs of Limited Nesting and Count of Lengths. Reviewed International coauthorship

    Pavel Klavík, Yota Otachi, Jirí Sejnoha

    Algorithmica   Vol. 81 ( 4 ) page: 1490 - 1511   2019

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1007/s00453-018-0481-y

  34. On structural parameterizations of firefighting. Reviewed International coauthorship

    Bireswar Das, Murali Krishna Enduri, Masashi Kiyomi, Neeldhara Misra, Yota Otachi, I. Vinod Reddy, Shunya Yoshimura

    Theor. Comput. Sci.   Vol. 782   page: 79 - 90   2019

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1016/j.tcs.2019.02.032

  35. On Computational Complexity of Pipe Puzzles. Reviewed

    Takumu Shirayama, Takuto Shigemura, Yota Otachi, Shuichi Miyazaki, Ryuhei Uehara

    IEICE Transactions   Vol. 102 ( 9 ) page: 1134 - 1141   2019

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1587/transfun.E102.A.1134

  36. Reconfiguration of colorable sets in classes of perfect graphs. Reviewed

    Takehiro Ito, Yota Otachi

    Theor. Comput. Sci.   Vol. 772   page: 111 - 122   2019

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1016/j.tcs.2018.11.024

  37. Token Sliding on Split Graphs. Reviewed International coauthorship

    Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora

    Leibniz International Proceedings in Informatics   Vol. 126   page: 13:1-13:17   2019

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.STACS.2019.13

  38. Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity Reviewed International coauthorship

    Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

    Algorithmica   Vol. 80 ( 7 ) page: 2160 - 2180   2018.7

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:Springer New York LLC  

    The problem MaxW-Light (MaxW-Heavy) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-Light is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MaxW-Heavy can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MaxW-Light, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin et al. (SIAM J Comput 44:54–87, 2015). The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

    DOI: 10.1007/s00453-017-0399-9

    Scopus

  39. Swapping colored tokens on graphs Reviewed International coauthorship

    Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno

    Theoretical Computer Science   Vol. 729   page: 1 - 10   2018.6

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:Elsevier B.V.  

    We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1,2,…,c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for c=3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded.

    DOI: 10.1016/j.tcs.2018.03.016

    Scopus

  40. Reconfiguration of colorable sets in classes of perfect graphs Reviewed

    Takehiro Ito, Yota Otachi

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 101   page: 271 - 2713   2018.6

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (reconfiguration) between two c-colorable sets in the same graph. This problem generalizes the well-studied Independent Set Reconfiguration problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial-time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for Feedback Vertex Set Reconfiguration.

    DOI: 10.4230/LIPIcs.SWAT.2018.27

    Scopus

  41. Parameterized orientable deletion Reviewed International coauthorship

    Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 101   page: 241 - 2413   2018.6

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    A graph is d-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most d. d-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-Orientable Deletion problem: given a graph G = (V, E), delete the minimum number of vertices to make G d-orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: We show that the problem is W[2]-hard and log n-inapproximable with respect to k, the number of deleted vertices. This closes the gap in the problem’s approximability. We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by d + k, but W-hard for each of the parameters d, k separately. We show that, under the SETH, for all d, , the problem does not admit a (d + 2 − )tw, algorithm where tw is the graph’s treewidth, resolving as a special case an open problem on the complexity of PseudoForest Deletion. We show that the problem is W-hard parameterized by the input graph’s clique-width. Complementing this, we provide an algorithm running in time dO(d·cw), showing that the problem is FPT by d + cw, and improving the previously best know algorithm for this case.

    DOI: 10.4230/LIPIcs.SWAT.2018.24

    Scopus

  42. How Bad is the Freedom to Flood-It? Reviewed International coauthorship

    Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 100   page: 51 - 513   2018.6

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    FIXED-FLOOD-IT and FREE-FLOOD-IT are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is to produce a monochromatic ("flooded") graph as quickly as possible. Their difference is that in FREE-FLOOD-IT the player has the additional freedom of choosing the vertex to play in each move. In this paper, we investigate how this freedom affects the complexity of the problem. It turns out that the freedom is bad in some sense. We show that some cases trivially solvable for FIXED-FLOOD-IT become intractable for FREE-FLOOD-IT. We also show that some tractable cases for FIXED-FLOOD-IT are still tractable for FREE-FLOOD-IT but need considerably more involved arguments. We finally present some combinatorial properties connecting or separating the two problems. In particular, we show that the length of an optimal solution for FIXED-FLOOD-IT is always at most twice that of FREE-FLOOD-IT, and this is tight.

    DOI: 10.4230/LIPIcs.FUN.2018.5

    Scopus

  43. A faster parameterized algorithm for PSEUDOFOREST DELETION Reviewed International coauthorship

    Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

    Discrete Applied Mathematics   Vol. 236   page: 42 - 56   2018.2

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:Elsevier B.V.  

    A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3knkO(1)) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. (2015) who gave a (nonlinear) 7.56knO(1)-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

    DOI: 10.1016/j.dam.2017.10.018

    Scopus

  44. Space-effcient algorithms for longest increasing subsequence Reviewed International coauthorship

    Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 96   page: 44:1-44:15   2018.2

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O(n log n) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n = s = n, we present algorithms that use O(s log n) bits and O(1 s · n2 · log n) time for computing the length of a longest increasing subsequence, and O(1 s · n2 · log2 n) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.

    DOI: 10.4230/LIPIcs.STACS.2018.44

    Scopus

  45. Induced Minor Free Graphs: Isomorphism and Clique-Width Reviewed International coauthorship

    Rémy Belmonte, Yota Otachi, Pascal Schweitzer

    Algorithmica   Vol. 80 ( 1 ) page: 29 - 47   2018.1

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:Springer New York LLC  

    Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is GI-complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. These two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor, or subgraph.

    DOI: 10.1007/s00453-016-0234-8

    Scopus

  46. Vertex deletion problems on chordal graphs Reviewed International coauthorship

    Yixin Cao, Yuping Ke, Yota Otachi, Jie You

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 93   page: 22:1-22:14 - 86   2018.1

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.

    DOI: 10.4230/LIPIcs.FSTTCS.2017.22

    Scopus

  47. Vertex deletion problems on chordal graphs. Reviewed International coauthorship

    Yixin Cao, Yuping Ke, Yota Otachi, Jie You

    Theor. Comput. Sci.   Vol. 745   page: 75-86   2018

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.1016/j.tcs.2018.05.039

  48. Computational Complexity of Robot Arm Simulation Problems. Reviewed

    Tianfeng Feng, Takashi Horiyama, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Ryuhei Uehara

    Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings   Vol. 10979   page: 177 - 188   2018

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:Springer  

    DOI: 10.1007/978-3-319-94667-2_15

  49. Exact Algorithms for the Max-Min Dispersion Problem. Reviewed

    Toshihiro Akagi, Tetsuya Araki, Takashi Horiyama, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa

    Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Guangzhou, China, May 8-10, 2018, Proceedings   Vol. 10823   page: 263 - 272   2018

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

    DOI: 10.1007/978-3-319-78455-7_20

  50. Safe sets in graphs: Graph classes and structural parameters Reviewed International coauthorship

    Raquel Águeda, Nathann Cohen, Shinya Fujita, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Hirotaka Ono, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu

    Journal of Combinatorial Optimization   Vol. 36 ( 4 ) page: 1 - 22   2017.11

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:Springer New York LLC  

    A safe set of a graph (Formula presented.) is a non-empty subset S of V such that for every component A of G[S] and every component B of (Formula presented.), we have (Formula presented.) whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.

    DOI: 10.1007/s10878-017-0205-2

    Scopus

  51. Hitori numbers Reviewed

    Akira Suzuki, Masashi Kiyomi, Yota Otachi, Kei Uchizawa, Takeaki Uno

    Journal of Information Processing   Vol. 25   page: 695 - 707   2017.8

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:Information Processing Society of Japan  

    Hitori is a popular “pencil-and-paper” puzzle defined as follows. In n-hitori, we are given an n×n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules are satisfied: Rule 1) No row or column has a repeated unpainted label
    Rule 2) Painted squares are never (horizontally or vertically) adjacent
    Rule 3) The unpainted squares are all connected (via horizontal and vertical connections). The grid is called an instance of n-hitori if it has a unique solution. In this paper, we introduce hitori number and maximum hitori number which are defined as follows: For every integer n, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. For every integer n, maximum hitori number h(n) is the maximum number of different integers used in an instance where the maximum is taken over all the instances of n-hitori. We then prove that ⌊(2n - 1)/3⌋ ≤ h(n) ≤ 2⌊n/3⌋ + 1 for n ≥ 2 and ⌊(4n2 - 4n + 11)/5⌋ ≥ h(n) ≤ (4n2 + 2n - 2)/5 for n ≤ 3.

    DOI: 10.2197/ipsjjip.25.695

    Scopus

  52. Extending Partial Representations of Interval Graphs Reviewed International coauthorship

    Pavel Klavik, Jan Kratochvil, Yota Otachi, Toshiki Saitoh, Tomas Vyskoil

    ALGORITHMICA   Vol. 78 ( 3 ) page: 945 - 967   2017.7

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:SPRINGER  

    Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph G can be represented by closed intervals, i.e., whether G is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, the oldest one is by Booth and Lueker (J Comput Syst Sci 13: 335-379, 1976) based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension. The input of this problem consists of a graph G with a partial representation R' fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation R of the entire graph G extending R'. We generalize the characterization of interval graphs by Fulkerson and Gross (Pac J Math 15: 835-855, 1965) to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.

    DOI: 10.1007/s00453-016-0186-z

    Web of Science

  53. Alliances in graphs of bounded clique-width Reviewed

    Masashi Kiyomi, Yota Otachi

    DISCRETE APPLIED MATHEMATICS   Vol. 223   page: 91 - 97   2017.5

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    An alliance in a graph is a set of vertices that is either safe under attacks from the neighborhood (defensive), capable of attacking its neighbors (offensive), or simultaneously defensive and offensive (powerful). An alliance is global if all nonmembers are adjacent to some members of the alliance. The concept of alliances was introduced by Kristiansen et al. (2004). After that many results concerning the complexity for finding a minimum alliance were shown. It was shown that the problem of finding a minimum alliance of any variant is NP-hard in general. For some variants, it was shown that the problem becomes polynomial time solvable when restricted to trees or series-parallel graphs.
    In this paper, we show that the problems for all variants are efficiently solvable for much larger graph classes. We present a polynomial-time algorithm for graphs of bounded clique-width. We also show that the problem is fixed-parameter tractable when parameterized by the vertex cover number. (C) 2017 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2017.02.004

    Web of Science

  54. Extending Partial Representations of Proper and Unit Interval Graphs Reviewed International coauthorship

    Pavel Klavik, Jan Kratochvil, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, Tomas Vyskocil

    ALGORITHMICA   Vol. 77 ( 4 ) page: 1071 - 1104   2017.4

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:SPRINGER  

    The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations. We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of some intervals by lower and upper bounds. We show that this problem is NP-complete for disconnected input graphs and give a polynomial-time algorithm for the special class of instances, where the ordering of the connected components of the input graph along the real line is prescribed. This includes the case of partial representation extension. The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs (Balko et al. in 2013). So unless , proper and unit interval representations have vastly different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques.

    DOI: 10.1007/s00453-016-0133-z

    Web of Science

  55. A faster parameterized algorithm for pseudoforest deletion Reviewed International coauthorship

    Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 63   page: 7:1-7:12   2017.2

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3knkO(1)) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. [MFCS 2015] who gave a (nonlinear) 7.56knO(1)-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

    DOI: 10.4230/LIPIcs.IPEC.2016.7

    Scopus

  56. Thin strip graphs Reviewed

    Takashi Hayashi, Akitoshi Kawamura, Yota Otachi, Hidehiro Shinohara, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   Vol. 216   page: 203 - 210   2017.1

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    A unit disk graph is a c-strip graph if it has a unit disk representation in which all centers of the unit disks lie between two parallel lines at distance c. The classes of c-strip graphs for various c are studied in the literature. For example, the 0-strip graphs are exactly the unit interval graphs, and every root 3/2-strip graph is a co-comparability graph. In this paper, we introduce the class of thin strip graphs and study their properties. A graph is a thin strip graph if it is a c-strip graph for every c > 0. We show that there is no constant t such that the t-strip graphs are exactly the thin strip graphs. We also show that the class of thin strip graphs properly includes the class of mixed unit interval graphs. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2015.01.018

    Web of Science

  57. Ferrers dimension of grid intersection graphs Reviewed International coauthorship

    Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara

    DISCRETE APPLIED MATHEMATICS   Vol. 216   page: 130 - 135   2017.1

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    We investigate the Ferrers dimension of classes of grid intersection graphs and show properties and characterizations. In particular, we show that (1) the grid intersection graphs form a proper subclass of the class of bipartite graphs of Ferrers dimension 4, (2) segment-ray graphs have a forbidden submatrix characterization, and (3) a bipartite graph is a unit grid intersection graph if and only if it is the intersection of two bipartite permutation graphs. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2015.05.035

    Web of Science

  58. Efficient enumeration of maximal k-degenerate subgraphs in a chordal graph Reviewed International coauthorship

    Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, Kunihiro Wasa

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 10392   page: 150 - 161   2017

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer Verlag  

    In this paper, we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m\\cdot \\omega (G)) for any n-vertex chordal graph with m edges, where \\omega (G) \\le n is the maximum size of a clique in G. The problem generalizes that of enumerating maximal independent sets and maximal induced forests, which correspond to respectively 0-degenerate and 1-degenerate subgraphs.

    DOI: 10.1007/978-3-319-62389-4_13

    Scopus

  59. Degree-constrained orientation of maximum satisfaction: Graph classes and parameterized complexity Reviewed International coauthorship

    Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 64   page: 20.1 - 20.12   2016.12

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    The problem MAX W-LIGHT (MAX W-HEAVY) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-LIGHT is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MAX W-HEAVY can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MAX W-LIGHT, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin, Todinca, and Villanger [SIAM J. Comput., 44(1):57-87, 2015]. The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

    DOI: 10.4230/LIPIcs.ISAAC.2016.20

    Scopus

  60. On the classes of interval graphs of limited nesting and count of lengths Reviewed International coauthorship

    Pavel Klavík, Yota Otachi, Jiří Šejnoha

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 64   page: 45.1 - 45.13   2016.12

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    In 1969, Roberts introduced proper and unit interval graphs and proved that these classes are equal. Natural generalizations of unit interval graphs called k-length interval graphs were considered in which the number of different lengths of intervals is limited by k. Even after decades of research, no insight into their structure is known and the complexity of recognition is open even for k = 2. We propose generalizations of proper interval graphs called k-nested interval graphs in which there are no chains of k + 1 intervals nested in each other. It is easy to see that k-nested interval graphs are a superclass of k-length interval graphs. We give a linear-time recognition algorithm for k-nested interval graphs. This algorithm adds a missing piece to Gajarský et al. [FOCS 2015] to show that testing FO properties on interval graphs is FPT with respect to the nesting k and the length of the formula, while the problem is W[2]-hard when parameterized just by the length of the formula. Further, we show that a generalization of recognition called partial representation extension is polynomial-time solvable for k-nested interval graphs, while it is NP-hard for k-length interval graphs, even when k = 2.

    DOI: 10.4230/LIPIcs.ISAAC.2016.45

    Scopus

  61. Finding a chain graph in a bipartite permutation graph Reviewed

    Masashi Kiyomi, Yota Otachi

    INFORMATION PROCESSING LETTERS   Vol. 116 ( 9 ) page: 569 - 573   2016.9

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    We present a polynomial-time algorithm for solving SUBGRAPH ISOMORPHISM where the base graphs are bipartite permutation graphs and the pattern graphs are chain graphs. (C) 2016 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.ip1.2016.04.006

    Web of Science

  62. A lower bound on opaque sets Reviewed International coauthorship

    Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, János Pach

    Leibniz International Proceedings in Informatics, LIPIcs   Vol. 51   page: 46.1 - 46.10   2016.6

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle.

    DOI: 10.4230/LIPIcs.SoCG.2016.46

    Scopus

  63. Polynomial-time algorithms for SUBGRAPH ISOMORPHISM in small graph classes of perfect graphs Reviewed

    Matsuo Konagaya, Yota Otachi, Ryuhei Uehara

    DISCRETE APPLIED MATHEMATICS   Vol. 199   page: 37 - 45   2016.1

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    Given two graphs, SUBGRAPH ISOMORPHISM is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time.
    In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. (2012). To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2015.01.040

    Web of Science

  64. On the treewidth of toroidal grids Reviewed

    Masashi Kiyomi, Yoshio Okamoto, Yota Otachi

    DISCRETE APPLIED MATHEMATICS   Vol. 198   page: 303 - 306   2016.1

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    Many graph parameters of grid-like graphs are studied because of their algorithmic consequences. An important concept in this context is that of treewidth. Treewidth of graphs is a graph parameter for measuring how close a graph is to a tree. In this paper, we study the treewidth of toroidal grids and show that the treewidth of the n x n toroidal grid is either 2n - 2 or 2n - 1. We then show that these bounds are tight in some cases. To show the lower bounds, we construct brambles of high orders. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2015.06.027

    Web of Science

  65. A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares Reviewed

    Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS   Vol. 51   page: 25 - 39   2016.1

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen [9] introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen [21] before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.comgeo.2015.10.004

    Web of Science

  66. Induced Minor Free Graphs: Isomorphism and Clique-width Reviewed International coauthorship

    Remy Belmonte, Yota Otachi, Pascal Schweitzer

    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE   Vol. 9224   page: 299 - 311   2016

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is isomorphism complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. Those two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor or subgraph.

    DOI: 10.1007/978-3-662-53174-7_21

    Web of Science

  67. Safe sets in graphs: Graph classes and structural parameters Reviewed International coauthorship

    Raquel Águeda, Nathann Cohen, Shinya Fujita, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 10043   page: 241 - 253   2016

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer Verlag  

    A safe set of a graph G = (V,E) is a non-empty subset S of V such that for every component A of G[S] and every component B of G[V \\ S], we have |A| ≥ |B| whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.

    DOI: 10.1007/978-3-319-48749-6_18

    Scopus

  68. Linear-time algorithm for sliding tokens on trees Reviewed International coauthorship

    Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada

    THEORETICAL COMPUTER SCIENCE   Vol. 600   page: 132 - 142   2015.10

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar l(b)vertical bar =vertical bar I-r vertical bar and imagine that a token is placed on each vertex in I-b. Then, the SLIDING TOKEN problem is to determine whether there exists a sequence of independent sets which transforms I-b into I-r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between I-b and I-r whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2015.07.037

    Web of Science

  69. Extending partial representations of subclasses of chordal graphs Reviewed International coauthorship

    Pavel Klavik, Jan Kratochvil, Yota Otachi, Toshiki Saitoh

    THEORETICAL COMPUTER SCIENCE   Vol. 576   page: 85 - 101   2015.4

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T' and some pre-drawn subtrees of T'. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i.e., keeps the pre-drawn subtrees unchanged).
    We consider four modifications of T' leading to vastly different problems: (i) T = T', (ii) T is a subdivision of T', (iii) T is a supergraph of T', and (iv) T' is a topological minor of T. In some cases, it is interesting to consider the complexity even when just T' is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. We further study the parametrized complexity of the problems when parametrized by the number of pre-drawn subtrees, the number of components of the input graph G and the size of the tree T'.
    We describe an interesting relation with integer partition problems. The problem 3-PARTITION is used for all NP-completeness reductions. When the space in T' is limited, partial representation extension of proper interval graphs is "equivalent" to the BINPACKING problem. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2015.02.007

    Web of Science

  70. Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds Reviewed International coauthorship

    Kazuyuki Amano, Kyaw May Oo, Yota Otachi, Ryuhei Uehara

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS   Vol. E98D ( 3 ) page: 486 - 489   2015.3

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

    Secure sets and defensive alliances in graphs are studied. They are sets of vertices that are safe in some senses. In this paper, we first present a fixed-parameter algorithm for finding a small secure set, whose running time ismuch faster than the previously known one. We then present improved bound on the smallest sizes of defensive alliances and secure sets for hypercubes. These results settle some open problems paused recently.

    DOI: 10.1587/transinf.2014FCP0007

    Web of Science

    Other Link: http://dblp.uni-trier.de/db/journals/ieicet/ieicet98d.html#journals/ieicet/AmanoOOU15

  71. Swapping colored tokens on graphs Reviewed International coauthorship

    Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 9214   page: 619 - 628   2015

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer Verlag  

    We investigate the computational complexity of the following problem. We are given a graph in which each vertex has the current and target colors. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1, 2,..., c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for every constant c ≥ 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees.

    DOI: 10.1007/978-3-319-21840-3_51

    Scopus

  72. COMPLETELY INDEPENDENT SPANNING TREES IN (PARTIAL) k-TREES Reviewed

    Masayoshi Matsushita, Yota Otachi, Toru Araki

    DISCUSSIONES MATHEMATICAE GRAPH THEORY   Vol. 35 ( 3 ) page: 427 - 437   2015

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:UNIV ZIELONA GORA  

    Two spanning trees T-1 and T-2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T-1 and T-2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree.
    First we show that [k/2] <= cist(G) <= k - 1 for any k-tree G. Then we show that for any p is an element of {[k/2],..., k - 1}, there exist infinitely many k-trees G such that cist(G) = p. Finally we consider algorithmic aspects for computing cist(G). Using Courcelle's theorem, we show that there is a linear-time algorithm that computes cist(G) for a partial k-tree, where k is a fixed constant.

    DOI: 10.7151/dmgt.1806

    Web of Science

  73. Competitive diffusion on weighted graphs Reviewed

    Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka, Xiao Zhou

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 9214   page: 422 - 433   2015

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer Verlag  

    Consider an undirected and vertex-weighted graph modeling a social network, where the vertices represent individuals, the edges do connections among them, and weights do levels of importance of individuals. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her idea which spreads along the edges in the graph. The objective of every player is to maximize the sum of weights of vertices infected by his/her idea. In this paper, we study a computational problem of asking whether a pure Nash equilibrium exists in a given graph, and present several negative and positive results with regard to graph classes. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forests of paths with arbitrary weights is solvable in pseudo-polynomial time
    and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem is solvable in polynomial time for chain graphs, cochain graphs, and threshold graphs with arbitrary integer weights.

    DOI: 10.1007/978-3-319-21840-3_35

    Scopus

  74. Reconfiguration of Cliques in a Graph Reviewed

    Takehiro Ito, Hirotaka Ono, Yota Otachi

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015)   Vol. 9076   page: 212 - 223   2015

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. In particular, the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs.

    DOI: 10.1007/978-3-319-17142-5_19

    Web of Science

  75. Sliding Token on Bipartite Permutation Graphs Reviewed International coauthorship

    Eli Fox-Epstein, Duc A. Hoang, Yota Otachi, Ryuhei Uehara

    ALGORITHMS AND COMPUTATION, ISAAC 2015   Vol. 9472   page: 237 - 247   2015

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER INT PUBLISHING AG  

    Sliding Token is a natural reconfiguration problem in which vertices of independent sets are iteratively replaced by neighbors. We develop techniques that may be useful in answering the conjecture that Sliding Token is polynomial-time decidable on bipartite graphs. Along the way, we give efficient algorithms for Sliding Token on bipartite permutation and bipartite distance-hereditary graphs.

    DOI: 10.1007/978-3-662-48971-0_21

    Web of Science

  76. Base-object location problems for base-monotone regions Reviewed

    Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno

    THEORETICAL COMPUTER SCIENCE   Vol. 555   page: 71 - 84   2014.10

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    A base-monotone region with a base is a subset of the cells in a pixel grid such that if a cell is contained in the region then so are the ones on a shortest path from the cell to the base. The problem of decomposing a pixel grid into disjoint base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and base-lines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions with respect to the given baselines (Chun et al., 2012 [4]). We continue this line of research and show the NP-hardness of the problem of optimally locating k base-lines in a given n x n pixel grid. We then present an O (n(3))-time 2-approximation algorithm for this problem. We also study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. (C) 2013 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2013.11.030

    Web of Science

  77. Efficient algorithms for network localization using cores of underlying graphs Reviewed

    Meng Li, Yota Otachi, Takeshi Tokuyama

    THEORETICAL COMPUTER SCIENCE   Vol. 553   page: 18 - 26   2014.10

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    Network localization is important for networks with no prefixed positions of network nodes such as sensor networks. We are given a subset of the set of ((n)(2)) pairwise distances among n sensors in some Euclidean space. We want to determine the positions of each sensor from the (partial) distance information. The input can be seen as an edge weighted graph. In this paper, we present some efficient algorithms that solve this problem using the structures of input graphs, which we call their cores. For instance, we present a polynomial-time algorithm solving the network localization problem for graphs with connected dominating sets of bounded size. This algorithm allows us to have fixed-parameter tractable algorithms for some restricted instances such as graphs with connected vertex covers of bounded size. (C) 2014 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2014.02.020

    Web of Science

  78. A 4.31-approximation for the geometric unique coverage problem on unit disks Reviewed

    Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    THEORETICAL COMPUTER SCIENCE   Vol. 544   page: 14 - 31   2014.8

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2 +4/root 3+epsilon (<4.3095+epsilon) for any fixed constant epsilon>0. Our algorithm runs in polynomial time which depends exponentially on 1/epsilon. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. (C) 2014 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2014.04.014

    Web of Science

  79. Approximating the path-distance-width for AT-free graphs and graphs in related classes Reviewed

    Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   Vol. 168   page: 69 - 77   2014.5

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    We consider the problem of determining the path-distance-width for AT-free graphs and graphs in related classes such as k-cocomparability graphs, proper interval graphs, cobipartite graphs, and cochain graphs. We first show that the problem is NP-hard even for cobipartite graphs, and thus for AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for AT-free graphs and graphs in the related graph classes mentioned above. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for cochain graphs, which form a subclass of the class of proper interval graphs.(c) 2012 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2012.11.015

    Web of Science

  80. Lower bounds for treewidth of product graphs Reviewed

    Kyohei Kozawa, Yota Otachi, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   Vol. 162   page: 251 - 258   2014.1

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    Two lower bounds for the treewidth of product graphs are presented in terms of the bramble number. The first bound is that the bramble number of the Cartesian product of graphs G(1) and G(2) must be at least the product of the Hadwiger number of G(1) and the PI number of G(2), where the PI number is a new graph parameter introduced in this paper. The second bound is that the bramble number of the strong product of graphs G(1) and G(2) must be at least the product of the Hadwiger number of G(1) and the bramble number of G(2). We also demonstrate applications of the lower bounds. (C) 2013 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2013.08.005

    Web of Science

  81. Intersection Dimension of Bipartite Graphs Reviewed International coauthorship

    Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014)   Vol. 8402   page: 323 - 340   2014

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    We introduce a concept of intersection dimension of a graph with respect to a graph class. This generalizes Ferrers dimension, boxicity, and poset dimension, and leads to interesting new problems. We focus in particular on bipartite graph classes defined as intersection graphs of two kinds of geometric objects. We relate well-known graph classes such as interval bigraphs, two-directional orthogonal ray graphs, chain graphs, and (unit) grid intersection graphs with respect to these dimensions. As an application of these graph-theoretic results, we show that the recognition problems for certain graph classes are NP-complete.

    DOI: 10.1007/978-3-319-06089-7_23

    Web of Science

  82. Polynomial-Time Algorithms for SUBGRAPH ISOMORPHISM in Small Graph Classes of Perfect Graphs Reviewed

    Matsuo Konagaya, Yota Otachi, Ryuhei Uehara

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014)   Vol. 8402   page: 216 - 228   2014

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second graph (the pattern graph). This problem is NP-complete for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time.
    In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. [Discrete Math. 312, pp. 3164-3173, 2012]. To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete.

    DOI: 10.1007/978-3-319-06089-7_15

    Web of Science

  83. Reduction Techniques for Graph Isomorphism in the Context of Width Parameters Reviewed International coauthorship

    Yota Otachi, Pascal Schweitzer

    ALGORITHM THEORY - SWAT 2014   Vol. 8503   page: 368 - +   2014

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    We study the parameterized complexity of the graph isomorphism problem when parameterized by width parameters related to tree decompositions. We apply the following technique to obtain fixed-parameter tractability for such parameters. We first compute an isomorphism invariant set of potential bags for a decomposition and then apply a restricted version of the Weisfeiler-Lehman algorithm to solve isomorphism. With this we show fixed-parameter tractability for several parameters and provide a unified explanation for various isomorphism results concerned with parameters related to tree decompositions.
    As a possibly first step towards intractability results for parameterized graph isomorphism we develop an fpt Turing-reduction from strong tree width to the a priori unrelated parameter maximum degree.

    DOI: 10.1007/978-3-319-08404-6_32

    Web of Science

  84. Extending Partial Representations of Proper and Unit Interval Graphs Reviewed International coauthorship

    Pavel Klavik, Jan Kratochvil, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, Tomas Vyskocil

    ALGORITHM THEORY - SWAT 2014   Vol. 8503   page: 253 - +   2014

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations.
    We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of intervals by lower and upper bounds. We show that this problem is NP-complete for disconnected input graphs and give a polynomial-time algorithm for a special class of instances, where the ordering of the connected components of the input graph along the real line is fixed. This includes the case of partial representation extension.
    The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs [Balko et al. ISAAC'13]. So unless P = NP, proper and unit interval representations have very different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques.

    DOI: 10.1007/978-3-319-08404-6_22

    Web of Science

  85. Depth-First Search Using O(n) Bits Reviewed International coauthorship

    Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, Ryuhei Uehara

    ALGORITHMS AND COMPUTATION, ISAAC 2014   Vol. 8889   page: 553 - 564   2014

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    We provide algorithms performing Depth-First Search (DFS) on a directed or undirected graph with n vertices and m edges using only O(n) bits. One algorithm uses O(n) bits and runs in O(mlog n) time. Another algorithm uses n+ o(n) bits and runs in polynomial time. Furthermore, we show that DFS on a directed acyclic graph can be done in space n/2(Omega(root log n)) and in polynomial time, and we also give a simple linear-time O(log n)-space algorithm for the depth-first traversal of an undirected tree. Finally, we also show that for a graph having an O(1)-size feedback set, DFS can be done in O(log n) space. Our algorithms are based on the analysis of properties of DFS and applications of the s-t connectivity algorithms due to Reingold and Barnes et al., both of which run in sublinear space.

    DOI: 10.1007/978-3-319-13075-0_44

    Web of Science

  86. Polynomial-Time Algorithm for Sliding Tokens on Trees Reviewed International coauthorship

    Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada

    ALGORITHMS AND COMPUTATION, ISAAC 2014   Vol. 8889   page: 389 - 400   2014

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar I-b vertical bar = vertical bar I-r vertical bar, and imagine that a token is placed on each vertex in I-b. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I-b and I-r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we show that the problem is solvable for trees in quadratic time. Our proof is constructive: for a yes-instance, we can find an actual sequence of independent sets between I-b and I-r whose length (i. e., the number of token-slides) is quadratic. We note that there exists an infinite family of instances on paths for which any sequence requires quadratic length.

    DOI: 10.1007/978-3-319-13075-0_31

    Web of Science

  87. Base location problems for base-monotone regions Reviewed

    Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 7748   page: 53 - 64   2013

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

    The problem of decomposing a pixel grid into base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and baselines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. We continue this line of research and show the NP-hardness of the problem of optimally locating k baselines in a given n ×n pixel grid. We also present an O(n3)-time 2-approximation algorithm for this problem. We then study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. © 2013 Springer-Verlag.

    DOI: 10.1007/978-3-642-36065-7_7

    Scopus

  88. On complexity of flooding games on graphs with interval representations Reviewed

    Hiroyuki Fukui, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 8296   page: 73 - 84   2013

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

    The flooding games, which are called Flood-It, Mad Virus, or HoneyBee, are a kind of coloring games and they have been becoming popular online. In these games, each player colors one specified cell in his/her turn, and all connected neighbor cells of the same color are also colored by the color. This flooding or coloring spreads on the same color cells. It is natural to consider the coloring games on general graphs: Once a vertex is colored, the flooding flows along edges in the graph. Recently, computational complexities of the variants of the flooding games on several graph classes have been studied. We investigate the one player flooding games on some graph classes characterized by interval representations. Our results state that the number of colors is a key parameter to determine the computational complexity of the flooding games. © 2013 Springer-Verlag.

    DOI: 10.1007/978-3-642-45281-9_7

    Scopus

  89. Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes Reviewed International coauthorship

    Yota Otachi, Pascal Schweitzer

    ALGORITHMS AND COMPUTATION   Vol. 8283   page: 111 - 118   2013

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    We study the graph isomorphism problem for graph classes defined by sets of forbidden subgraphs. We show that there is a complexity dichotomy in case the set of forbidden subgraphs is finite. More precisely, we show that the problem is polynomial-time solvable if the forbidden set contains a forest of subdivided stars and is graph isomorphism complete otherwise. We also show that, assuming that the graph isomorphism problem is not polynomial-time solvable in general, there is no such dichotomy for the cases of infinite sets of forbidden subgraphs. To this end, we conditionally show that there exists a graph class closed under taking subgraphs with intermediate isomorphism problem, i.e., a class on which the isomorphism problem is neither polynomial-time solvable nor graph isomorphism complete.

    DOI: 10.1007/978-3-642-45030-3_11

    Web of Science

  90. THE PATH-DISTANCE-WIDTH OF HYPERCUBES Reviewed

    Yota Otachi

    DISCUSSIONES MATHEMATICAE GRAPH THEORY   Vol. 33 ( 2 ) page: 467 - 470   2013

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:UNIV ZIELONA GORA  

    The path-distance-width of a connected graph G is the minimum integer w satisfying that there is a nonempty subset of S subset of V(G) such that the number of the vertices with distance i from S is at most w for any nonnegative integer i.
    In this note, we determine the path-distance-width of hypercubes.

    DOI: 10.7151/dmgt.1682

    Web of Science

  91. Bounded representations of interval and proper interval graphs Reviewed International coauthorship

    Martin Balko, Pavel Klavík, Yota Otachi

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 8283   page: 535 - 546   2013

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

    Klavík et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives a graph G and in addition for each vertex v two intervals ℒv and ℛv called bounds. We ask whether there exists a bounded representation in which each interval Iv has its left endpoint in ℒv and its right endpoint in . We show that the problem can be solved in linear time for interval graphs and in quadratic time for proper interval graphs. Robert's Theorem states that the classes of proper interval graphs and unit interval graphs are equal. Surprisingly, the bounded representation problem is polynomially solvable for proper interval graphs and NP-complete for unit interval graphs [Klavík et al., arxiv:1207.6960]. So unless P = NP, the proper and unit interval representations behave very differently. The bounded representation problem belongs to a wider class of restricted representation problems. These problems are generalizations of the well-understood recognition problem, and they ask whether there exists a representation of G satisfying some additional constraints. The bounded representation problems generalize many of these problems. © 2013 Springer-Verlag.

    DOI: 10.1007/978-3-642-45030-3_50

    Scopus

  92. Subgraph isomorphism in graph classes Reviewed

    Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno

    DISCRETE MATHEMATICS   Vol. 312 ( 21 ) page: 3164 - 3173   2012.11

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    We investigate the computational complexity of the following restricted variant of SUBGRAPH ISOMORPHISM: given a pair of connected graphs G = (V-G, E-G) and H = (V-H, E-H), determine if H is isomorphic to a spanning subgraph of G. The problem is NP-complete in general, and thus we consider cases where G and H belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of SUBGRAPH ISOMORPHISM such as HAMILTONIAN PATH, CLIQUE, BANDWIDTH, and GRAPH ISOMORPHISM can be solved in polynomial time, while these problems are hard in general. (c) 2012 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2012.07.010

    Web of Science

  93. Parameterized Complexity of the Spanning Tree Congestion Problem Reviewed International coauthorship

    Hans L. Bodlaender, Fedor V. Fomin, Petr A. Golovach, Yota Otachi, Erik Jan van Leeuwen

    ALGORITHMICA   Vol. 64 ( 1 ) page: 85 - 111   2012.9

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:SPRINGER  

    We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed ka parts per thousand yen8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for ka parts per thousand currency sign3 the problem becomes polynomially time solvable.

    DOI: 10.1007/s00453-011-9565-7

    Web of Science

  94. Efficient enumeration of ordered trees with k leaves Reviewed

    Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano

    THEORETICAL COMPUTER SCIENCE   Vol. 442   page: 22 - 27   2012.7

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    This paper presents a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n - k) time per tree, whereas our algorithm generates such trees in O(1) time per tree in the worst case. (C) 2011 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2011.01.017

    Web of Science

  95. Enumerating All Rooted Trees Including k Leaves Reviewed

    Masanobu Ishikawa, Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS   Vol. E95D ( 3 ) page: 763 - 768   2012.3

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

    This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3], [6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all "ordered" trees with 17 vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with it vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k = 1, 2, . . . , n - 1, we can also generate all rooted trees with exactly n vertices.

    DOI: 10.1587/transinf.E95.D.763

    Web of Science

    Other Link: http://dblp.uni-trier.de/db/journals/ieicet/ieicet95d.html#journals/ieicet/IshikawaYON12

  96. Random generation and enumeration of bipartite permutation graphs Reviewed

    Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara

    Journal of Discrete Algorithms   Vol. 10 ( 1 ) page: 84 - 97   2012.1

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected bipartite permutation graphs is proposed. The algorithm is based on reverse search, and it outputs each connected bipartite permutation graph in O(1) time. © 2011 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.jda.2011.11.001

    Scopus

  97. A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks Reviewed

    Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    ALGORITHMS AND COMPUTATION, ISAAC 2012   Vol. 7676   page: 372 - 381   2012

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2 + 4/root 3 + epsilon (< 4.3095 + epsilon) for any fixed constant epsilon > 0. Our algorithm runs in polynomial time which depends exponentially on 1/epsilon. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound.

    DOI: 10.1007/978-3-642-35261-4_40

    Web of Science

  98. A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares Reviewed

    Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 7357   page: 24 - 35   2012

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer  

    We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen (2009) before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. © 2012 Springer-Verlag.

    DOI: 10.1007/978-3-642-31155-0_3

    Scopus

  99. Isomorphism for Graphs of Bounded Connected-Path-Distance-Width Reviewed

    Yota Otachi

    ALGORITHMS AND COMPUTATION, ISAAC 2012   Vol. 7676   page: 455 - 464   2012

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    We show that Graph Isomorphism problem (GI) can be solved in O(n(2)) time for graphs of bounded connected-path-distance-width, and more generally, in O(n(c+1)) time for graphs of bounded c-connected-path-distance-width, where n is the number of vertices. These results extend the result of Yamazaki, Bodlaender, de Fluiter, and Thilikos [Isomorphism for graphs of bounded distance width. Algorithmica 24, 105-127 (1999)], who showed the fixed-parameter tractability of GI parameterized by rooted-path-distance-width.

    DOI: 10.1007/978-3-642-35261-4_48

    Web of Science

  100. Extending Partial Representations of Subclasses of Chordal Graphs Reviewed International coauthorship

    Pavel Klavik, Jan Kratochvil, Yota Otachi, Toshiki Saitoh

    ALGORITHMS AND COMPUTATION, ISAAC 2012   Vol. 7676   page: 444 - 454   2012

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    Chordal graphs are intersection graphs of subtrees in a tree. We investigate complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T' and some pre-drawn subtrees. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (keeps the pre-drawn subtrees unchanged).
    We consider four modifications of T' and get vastly different problems. In some cases, the problem is interesting even if just T' is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization.
    In addition, we study parametrized complexity by the number of pre-drawn subtrees, the number of components and the size of the tree T'. We describe an interesting relation with integer partition problems. The problem 3-Partition is used in the NP-completeness reductions. The BIN-PACKING problem is closely related to the extension of interval graphs when space in T' is limited, and we obtain "equivalency" with BIN PACKING.

    DOI: 10.1007/978-3-642-35261-4_47

    Web of Science

  101. On bipartite powers of bigraphs Reviewed

    Yoshio Okamoto, Yota Otachi, Ryuhei Uehara

    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE   Vol. 14 ( 2 ) page: 11-20   2012

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

  102. Spanning tree congestion of k-outerplanar graphs Reviewed International coauthorship

    Hans L. Bodlaender, Kyohei Kozawa, Takayoshi Matsushima, Yota Otachi

    DISCRETE MATHEMATICS   Vol. 311 ( 12 ) page: 1040 - 1045   2011.6

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    In 1987, Simonson conjectured that every k-outerplanar graph of maximum degree d has spanning tree congestion at most k . d [S. Simonson, A variation on the min cut linear arrangement problem, Math. Syst. Theory 20(1987)235-252]. We show that his conjecture is true and the bound is tight for outerplanar graphs and k-outerplanar graphs of maximum degree 4. We give a precise characterization of the spanning tree congestion of outerplanar graphs, and thus show that the spanning tree congestion of outerplanar graphs can be determined in linear time. (C) 2011 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2011.03.002

    Web of Science

  103. Bandwidth and pathwidth of three-dimensional grids Reviewed

    Yota Otachi, Ryohei Suda

    DISCRETE MATHEMATICS   Vol. 311 ( 10-11 ) page: 881 - 887   2011.6

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case. As a by-product, we also determine the two parameters of multi-dimensional grids with relatively large maximum factors. (C) 2011 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2011.02.019

    Web of Science

  104. Hardness results and an exact exponential algorithm for the spanning tree congestion problem Reviewed

    Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno

    Journal of Graph Algorithms and Applications   Vol. 15 ( 6 ) page: 727 - 751   2011

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential- time) exact algorithm that runs in O*(2 n) time, where n denotes the number of vertices. Additionally, we present simple combinatorial lem- mas, which yield a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.

    DOI: 10.7155/jgaa.00246

    Scopus

  105. Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem Reviewed

    Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011   Vol. 6648   page: 452 - 462   2011

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential-time) exact algorithm that runs in O*(2(n)) time, where n denotes the number of vertices. Additionally, we provide a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.

    DOI: 10.1007/978-3-642-20877-5_44

    Web of Science

  106. Spanning tree congestion of rook's graphs Reviewed

    Kyohei Kozawa, Yota Otachi

    Discussiones Mathematicae - Graph Theory   Vol. 31 ( 4 ) page: 753 - 761   2011

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:University of Zielona Gora  

    Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T ), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Km Kn for any m and n.

    DOI: 10.7151/dmgt.1577

    Scopus

  107. Approximability of the Path-Distance-Width for AT-free Graphs Reviewed

    Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki

    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE   Vol. 6986   page: 271 - +   2011

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    The path-distance-width of a graph measures how close the graph is to a path. We consider the problem of determining the path-distance-width for graphs with chain-like structures such as k-cocomparability graphs, AT-free graphs, and interval graphs. We first show that the problem is NP-hard even for a very restricted subclass of AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for graphs with chain-like structures. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for the class of cochain graphs, which is a subclass of the class of proper interval graphs.

    DOI: 10.1007/978-3-642-25870-1_25

    Web of Science

  108. The carving-width of generalized hypercubes Reviewed

    Yohei Kozawa, Yota Otachi, Koichi Yamazaki

    DISCRETE MATHEMATICS   Vol. 310 ( 21 ) page: 2867 - 2876   2010.11

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    The carving-width of a graph is the minimum congestion of routing trees for the graph. We determine the carving-width of generalized hypercubes: Hamming graphs, even grids, and tori. Our results extend the result of Chandran and Kavitha [L.S. Chandran, T. Kavitha, The carvingwidth of hypercubes, Discrete Math. 306 (2006) 2270-2274] that determines the carving-width of hypercubes. (C) 2010 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2010.06.039

    Web of Science

  109. Complexity Results for the Spanning Tree Congestion Problem Reviewed International coauthorship

    Yota Otachi, Hans L. Bodlaender, Erik Jan van Leeuwen

    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE   Vol. 6410   page: 3 - +   2010

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the complexity of this problem. First, we show that for every fixed k and d the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k >= 10. For very small values of k however, the problem becomes polynomially solvable. We also show that it is NP-hard to approximate the spanning tree congestion within a factor better than 11/10. On planar graphs, we prove the problem is NP-hard in general, but solvable in linear time for fixed k.

    DOI: 10.1007/978-3-642-16926-7_3

    Web of Science

  110. On spanning tree congestion of graphs Reviewed

    Kyohei Kozawa, Yota Otachi, Koichi Yamazaki

    DISCRETE MATHEMATICS   Vol. 309 ( 13 ) page: 4215 - 4224   2009.7

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    Let G be a connected graph and T be a spanning tree of G. For e is an element of E(T), the congestion of e is the number of edges in G connecting two components of T - e. The edge congestion of G in T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes. (C) 2008 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2008.12.021

    Web of Science

  111. Security number of grid-like graphs Reviewed

    Kyohei Kozawa, Yota Otachi, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   Vol. 157 ( 11 ) page: 2555 - 2561   2009.6

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    The security number of a graph is the cardinality of a smallest vertex subset of the graph Such that any attack on the subset is defendable. In this paper, we determine the security number of two-dimensional cylinders and tori. This result settles a conjecture of Brigham et al. [R.C. Brigham, R.D. Dutton, S.T. Hedetniemi, Security in graphs, Discrete Appl. Math. 155(2007)1708-1714]. (C) 2009 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2009.03.020

    Web of Science

  112. Efficient Enumeration of Ordered Trees with k Leaves Reviewed

    Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano

    WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS   Vol. 5431   page: 141 - +   2009

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    In this paper, we give a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n - k) time for each, while our algorithm generates Such trees in O(1) time for each in worst case.

    DOI: 10.1007/978-3-642-00202-1_13

    Web of Science

  113. Random Generation and Enumeration of Bipartite Permutation Graphs Reviewed

    Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   Vol. 5878   page: 1104 - +   2009

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:SPRINGER-VERLAG BERLIN  

    Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected bipartite permutation graphs is proposed. The algorithm is based on the reverse search, and it outputs each connected bipartite permutation graph in O(1) time.

    DOI: 10.1007/978-3-642-10631-6_111

    Web of Science

  114. An improved algorithm for the longest induced path problem on k-chordal graphs Reviewed

    Tetsuya Ishizeki, Yota Otachi, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   Vol. 156 ( 15 ) page: 3057 - 3059   2008.8

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    Gavril [F. Gavril, Algorithms for maximum weight induced paths, Information Processing Letters 81 (2002) 203-208] showed that the length of a longest induced path for graphs having no induced cycles on more than k vertices can be computed in O(n(k)m) time where n and m denote the number of vertices and edges, respectively. In this paper, we present an O(n(k)) time algorithm for the same problem. (C) 2008 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2008.01.019

    Web of Science

  115. A lower bound for the vertex boundary-width of complete k-ary trees Reviewed

    Yota Otachi, Koichi Yamazaki

    DISCRETE MATHEMATICS   Vol. 308 ( 12 ) page: 2389 - 2395   2008.6

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    The vertex boundary-width problem (for short VBWP) is to determine the value of vbw(G) = max(1 <= l <= vertical bar V vertical bar) min (S subset of V,vertical bar S vertical bar=l)vertical bar N(S)vertical bar for a given graph G = (V, E), where N(S) = {upsilon is not an element of S vertical bar upsilon is a neighbor of u for some u is an element of S}. In this paper, we give a lower bound for vertex boundary-width of complete k-ary trees. (C) 2007 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2007.05.014

    Web of Science

  116. Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs Reviewed

    Yota Otachi, Yoshio Okamoto, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   Vol. 155 ( 17 ) page: 2383 - 2390   2007.10

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:ELSEVIER SCIENCE BV  

    We show that the class of unit grid intersection graphs properly includes both of the classes of interval bigraphs and of P-6-free chordal bipartite graphs. We also demonstrate that the classes of unit grid intersection graphs and of chordal bipartite graphs are incomparable. (C) 2007 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2007.07.010

    Web of Science

▼display all

Presentations 12

  1. Exploring the gap between treedepth and vertex cover through vertex integrity International conference

    Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi

    The 12th International Conference on Algorithms and Complexity (CIAC 2021) 

     More details

    Event date: 2021.5

    Language:English   Presentation type:Oral presentation (general)  

  2. Fair MSO evaluation problems parameterized by vertex integrity

    2021.3.10 

     More details

    Event date: 2021.3

    Language:English   Presentation type:Oral presentation (general)  

  3. Finding diverse trees, paths, and more International conference

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi

    The 35th AAAI Conference on Artificial Intelligence (AAAI 2021) 

     More details

    Event date: 2021.2

    Language:English   Presentation type:Poster presentation  

  4. 黒どこに対する物理ゼロ知識証明プロトコル

    2021.2.3 

     More details

    Event date: 2021.2

    Language:Japanese   Presentation type:Oral presentation (general)  

  5. Parameterized complexity of graph burning International conference

    Yasuaki Kobayashi, Yota Otachi

    The 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) 

     More details

    Event date: 2020.12

    Language:English   Presentation type:Oral presentation (general)  

  6. An improved deterministic parameterized algorithm for cactus vertex deletion

    2020.12.4 

     More details

    Event date: 2020.12

    Language:English   Presentation type:Oral presentation (general)  

  7. Algorithms for Finding Diverse Subgraphs

    2020.9.30 

     More details

    Event date: 2020.9

    Language:English   Presentation type:Oral presentation (general)  

  8. Grundy distinguishes treewidth from pathwidth International coauthorship International conference

    Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi

    The 28th European Symposium on Algorithms (ESA 2020) 

     More details

    Event date: 2020.9

    Language:English   Presentation type:Oral presentation (general)  

  9. Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs International conference

    Taisuke Izumi, Yota Otachi

    The 47th International Colloquium on Automata, Languages and Programming (ICALP 2020) 

     More details

    Event date: 2020.7

    Language:English   Presentation type:Oral presentation (general)  

  10. Linear-time recognition of double-threshold graphs International conference

    Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno

    The 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020) 

     More details

    Event date: 2020.6

    Language:English   Presentation type:Oral presentation (general)  

  11. Parameterized complexity of (A, ℓ)-path packing International coauthorship International conference

    Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

    The 31st International Workshop on Combinatorial Algorithms (IWOCA 2020) 

     More details

    Event date: 2020.6

    Language:English   Presentation type:Oral presentation (general)  

  12. Hedonic seat arrangement problems (Extended abstract) International coauthorship International conference

    Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

    The 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2020) 

     More details

    Event date: 2020.5

    Language:English   Presentation type:Oral presentation (general)  

▼display all

Research Project for Joint Research, Competitive Funding, etc. 3

  1. パラメータ化近似グラフアルゴリズムのさらなる発展

    2019.4

    二国間交流事業共同研究 

    大舘陽太

      More details

    Grant type:Competitive

  2. 木構造を用いたネットワーク上での計算: 理論と実践

    2018.4 - 2019.3

    二国間交流事業セミナー 

    大舘陽太

      More details

    Grant type:Competitive

  3. パラメータ化近似グラフアルゴリズム

    2017.4 - 2019.3

    二国間交流事業共同研究 

    大舘陽太

      More details

    Grant type:Competitive

KAKENHI (Grants-in-Aid for Scientific Research) 10

  1. Refining the graph parameter hierarchy for fine-grained algorithms

    Grant number:21K11752  2021.4 - 2026.3

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Scientific Research (C)

      More details

    Authorship:Principal investigator 

    Grant amount:\4160000 ( Direct Cost: \3200000 、 Indirect Cost:\960000 )

  2. 計算機科学アプローチによる組合せ遷移の展開:アルゴリズムの自動生成に向けて

    Grant number:20H05793  2020.10 - 2023.3

    科学研究費助成事業  学術変革領域研究(B)

    伊藤 健洋, 和佐 州洋, 小林 靖明, 大舘 陽太, 山内 由紀子

      More details

    Authorship:Coinvestigator(s)  Grant type:Competitive

    A01班は計算機科学を背景分野とし,組合せ遷移に対するアルゴリズム的メタ定理の構築を目指す.現状,組合せ遷移のアルゴリズム開発は,個々の問題に対する事例研究の度合いが強い.本計画研究では,これら個別に開発されたアルゴリズム手法を「統一された設計技法」へと昇華し,これにより組合せ遷移のアルゴリズムを自動生成できるようにすることを目指す.

  3. Research on algorithms and data structures for solving theoretically hard problems in practical time

    Grant number:18H04091  2018.4 - 2023.3

    Grants-in-Aid for Scientific Research  Grant-in-Aid for Scientific Research (A)

      More details

    Authorship:Coinvestigator(s)  Grant type:Competitive

  4. 固定パラメータ困難問題に対する汎用解法の研究

    Grant number:18K11169  2018.4 - 2022.3

    科学研究費助成事業  基盤研究(C)

    清見 礼, 大舘 陽太

      More details

    Authorship:Coinvestigator(s)  Grant type:Competitive

    Grant amount:\2340000 ( Direct Cost: \1800000 、 Indirect Cost:\540000 )

    固定パラメータ困難問題に対する汎用アルゴリズムに関する研究として、関連する問題の計算複雑性等を研究し、今年度は主に以下の研究成果を得た。
    パスの端点と長さの上限が指定され、条件を満たすなるべく多くの点疎パスを見つけるという問題を、パラーメタ化計算量の観点から研究した。木幅とその他の問題依存パラメータの組合せに関して、容易な場合、困難な場合を解明した。また、木幅とパス幅に関して、それぞれをパラメータとしたときに計算量クラスが異なるような問題の具体例を示した。このような問題は今まで知られていなかった。さらに、情報拡散やプロセッサ間通信をモデル化した問題に対し、木構造パラメータに関する複数の未解決問題を解決した。この結果により,グラフ償却問題に対してほぼ完全な計算複雑性解明に成功した。ここでは、木構造パラメータを一般化した「グラフクラスへの距離」という概念も扱った。この概念の他の問題への適用や、汎用解法設計への応用も期待できる。さらに、グラフアルゴリズムにおいてもっと基本的な手続きの一つである幅優先探索について、木幅が小さければ劣線形空間の多項式時間アルゴリズムが存在することを示した。特に、木幅が小さいが定数とはみなせない場合について、木構造を空間計算量の改善に用いることに成功した。
    様々なパラメータに対して、複雑性やアルゴリズムに関する結果を得ているが、汎用解法に関してはまだあまり進んでいないので、今後は汎用解法についても研究を進めていかなくてはならない。
    新型コロナウィルスによる対策で国内外の出張が制限されており、分担者やその他の研究者と直接会って集中的に議論することができていない。研究は議論から生まれる部分が多いため、やや遅れが出てしまっている。
    様々なパラメータに関して、どのようなことができ、どのような問題は難しいかが分かってきているので、そこからより一般化された形の汎用解法を得ることを目指す。

  5. Speeding up FPT algorithms with special tree decompositions

    Grant number:18K11168  2018.4 - 2022.3

    Japan Society for the Promotion of Science  Grants-in-Aid for Scientific Research  Grant-in-Aid for Scientific Research (C)

      More details

    Authorship:Principal investigator  Grant type:Competitive

    Grant amount:\4420000 ( Direct Cost: \3400000 、 Indirect Cost:\1020000 )

  6. Fixed width parameter algorithms for the graph isomorphism problem

    Grant number:25730003  2013.4 - 2016.3

    Otachi Yota

      More details

    Authorship:Principal investigator  Grant type:Competitive

    Grant amount:\4160000 ( Direct Cost: \3200000 、 Indirect Cost:\960000 )

    We showed that the graph isomorphism problem is fixed-parameter tractable when parameterized by root-connected tree distance width. To show the result, we modified the classic Weisfeiler-Lehman algorithm so that it works not only for all vertex subsets of size k but also for restricted family of vertex subsets of size k. Furthermore, the modified algorithm runs in FPT time with the parameter k. Then we showed that we can apply the algorithm to the graph isomorphism problem parmeterized by several graph width parameters including root-connected tree distance width.
    We also studied the graph isomorphism problem for graph classes forbidding a single graph as an induced minor. We showed a complexity dichotomy with respect to the forbidden induced minor.

  7. Exploring the Limits of Computation in the Scenario of Constrained Work Space

    Grant number:24106004  2012.6 - 2017.3

    Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)

    Asano Tetsuo

      More details

    Authorship:Coinvestigator(s)  Grant type:Competitive

    Grant amount:\3640000 ( Direct Cost: \2800000 、 Indirect Cost:\840000 )

    In this research we have developed powerful techniques for analysis toward establishment of nontrivial lower and upper bounds on the constrained work space. The most fundamental problem is to seek for each entry in a given array of real numbers one of nearest greater values. Using linear size of work space we can design a linear time algorithm for solving the problem. Our problem is whether we can solve the problem in an efficient way using less work space. In this research we showed that we have an efficient algorithm using only constant amount of work space. We also had results on time and space tradeoffs on the problem. We obtained other many results in basic problems in computational geometry and graph theory.

  8. Development of Algorithmic Paradigms on Memory-Constrained Computation

    Grant number:23300001  2011.4 - 2015.3

    ASANO Tetsuo

      More details

    Authorship:Coinvestigator(s)  Grant type:Competitive

    Grant amount:\832000 ( Direct Cost: \640000 、 Indirect Cost:\192000 )

    With recent progressin computer environment,as the performance of computers is improved, people tend to be interested in larger-sized problems such as big-data processing. The problem size is continuously growing, we have a problem of too large memory size to be included in computer main memory. Because of this reason memory-constrained algorithms are requested in many ways, but research on small-memory algorithms has just begun. In this reserch we focus on computational geometry and develop memory-efficient algorithms,but we also developed efficient algorithms for graph problems and binary image processing problems.

  9. Designing low-congestion sparse networks

    Grant number:23800004  2011 - 2012

    JSPS  Grants-in-Aid for Scientific Research(研究活動スタート支援)  研究活動スタート支援

    OTACHI Yota

      More details

    Authorship:Principal investigator  Grant type:Competitive

    Grant amount:\3250000 ( Direct Cost: \2500000 、 Indirect Cost:\750000 )

    We studied the problem of designing low-congestion sparse networks. Especially, we studied the computational complexity of an optimization problem on graphs called “the spanning tree congestion problem.” We presented sharp contrasts between hard cases and easy cases. We also investigated the parameterized complexity of the problem and gave some dichotomies for the problem. Our results imply the problem is really hard to solve for most of the cases. Thus we designed some heuristic and approximation algorithm and obtained some partial results.

  10. Treewidth and related graph parameters

    Grant number:09J06878  2009.4 - 2011.3

    JSPS  Grant-in-Aid for Scientific Research(特別研究員奨励費)  特別研究員奨励費

    OTACHI Yota

      More details

    Authorship:Principal investigator  Grant type:Competitive

    Grant amount:\1400000 ( Direct Cost: \1400000 )

▼display all

 

Teaching Experience (On-campus) 5

  1. Linear Algebra I

    2020

  2. Linear Algebra II

    2020

  3. Mathematical Informatics 4

    2020

  4. Mathematical Informatics 3

    2020

  5. Introduction to Mathematical Informatics 2

    2020