Arrow Research search

Author name cluster

Yushi Uno

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
2 author rows

Possible papers

9

TCS Journal 2018 Journal Article

Swapping colored tokens on graphs

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

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.

Details DOI

TCS Journal 2018 Journal Article

Threes!, Fives, 1024!, and 2048 are hard

  • Stefan Langerman
  • Yushi Uno

We analyze the computational complexity of the popular computer games Threes! , 1024! , 2048 and many of their variants. For most known versions expanded to an m × n board, we show that it is NP-hard to decide whether a given starting position can be played to reach a specific (constant) tile value.

Details DOI

TCS Journal 2017 Journal Article

Hanabi is NP-hard, even for cheaters who look at their cards

  • Jean-François Baffier
  • Man-Kwun Chiu
  • Yago Diez
  • Matias Korman
  • Valia Mitsou
  • André van Renssen
  • Marcel Roeloffzen
  • Yushi Uno

In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among c colors and a number between 1 and n. The aim is to make, for each color, a pile of cards of that color with all increasing numbers from 1 to n. At each time during the game, each player holds h cards in hand. Cards are drawn sequentially from a deck and the players should decide whether to play, discard or store them for future use. One of the features of the game is that the players can see their partners' cards but not their own and information must be shared through hints. We introduce a single-player, perfect-information model and show that the game is intractable even for this simplified version where we forego both the hidden information and the multiplayer aspect of the game, even when the player can only hold two cards in her hand. On the positive side, we show that the decision version of the problem—to decide whether or not numbers from 1 through n can be played for every color—can be solved in (almost) linear time for some restricted cases.

Details DOI

TCS Journal 2016 Journal Article

Mining preserving structures in a graph sequence

  • Takeaki Uno
  • Yushi Uno

In the recent research of data mining, frequent structures in a sequence of graphs have been studied intensively, and one of the main concerns is changing structures along a sequence of graphs that can capture dynamic properties of data. On the contrary, we newly focus on “preserving structures” in a graph sequence that satisfy a given property for a certain period, and mining such structures is studied. As for an onset, we bring up two structures, a connected vertex subset and a clique that exist for a certain period. We consider the problem of enumerating these structures. and present polynomial delay algorithms for the problems. Their running time may depend on the size of the representation, however, if each edge has at most one time interval in the representation, the running time is O ( | V | | E | 3 ) for connected vertex subsets and O ( min ⁡ { Δ 5, | E | 2 Δ } ) for cliques, where the input graph is G = ( V, E ) with maximum degree Δ. To the best of our knowledge, this is the first approach to the treatment of this notion, namely, preserving structures.

Details DOI

TCS Journal 2014 Journal Article

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

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

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 / 3 + ε ( < 4. 3095 + ε ) for any fixed constant ε > 0. Our algorithm runs in polynomial time which depends exponentially on 1 / ε. 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.

Details DOI

TCS Journal 2014 Journal Article

UNO is hard, even for a single player

  • Erik D. Demaine
  • Martin L. Demaine
  • Nicholas J.A. Harvey
  • Ryuhei Uehara
  • Takeaki Uno
  • Yushi Uno

This paper investigates the popular card game UNO® from the viewpoint of algorithmic combinatorial game theory. We define simple and concise mathematical models for the game, including both cooperative and uncooperative versions, and analyze their computational complexity. In particular, we prove that even a single-player version of UNO is NP-complete, although some restricted cases are in P. Surprisingly, we show that the uncooperative two-player version is also in P.

Details DOI

TCS Journal 2011 Journal Article

On the complexity of reconfiguration problems

  • Takehiro Ito
  • Erik D. Demaine
  • Nicholas J.A. Harvey
  • Christos H. Papadimitriou
  • Martha Sideri
  • Ryuhei Uehara
  • Yushi Uno

Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time.

Details DOI

TCS Journal 2009 Journal Article

An O ( n 1.75 ) algorithm for L ( 2, 1 ) -labeling of trees

  • Toru Hasunuma
  • Toshimasa Ishii
  • Hirotaka Ono
  • Yushi Uno

An L ( 2, 1 ) -labeling of a graph G is an assignment f from the vertex set V ( G ) to the set of nonnegative integers such that | f ( x ) − f ( y ) | ≥ 2 if x and y are adjacent and | f ( x ) − f ( y ) | ≥ 1 if x and y are at distance 2 for all x and y in V ( G ). A k - L ( 2, 1 ) -labeling is an L ( 2, 1 ) -labeling f: V ( G ) → { 0, …, k }, and the L ( 2, 1 ) -labeling problem asks the minimum k, which we denote by λ ( G ), among all possible L ( 2, 1 ) -labelings. It is known that this problem is NP-hard even for graphs of treewidth 2. Tree is one of a few classes for which the problem is polynomially solvable, but still only an O ( Δ 4. 5 n ) time algorithm for a tree T has been known so far, where Δ is the maximum degree of T and n = | V ( T ) |. In this paper, we first show that an existent necessary condition for λ ( T ) = Δ + 1 is also sufficient for a tree T with Δ = Ω ( n ), which leads to a linear time algorithm for computing λ ( T ) under this condition. We then show that λ ( T ) can be computed in O ( Δ 1. 5 n ) time for any tree T. Combining these, we finally obtain an O ( n 1. 75 ) time algorithm, which substantially improves upon previously known results.

Details DOI

MFCS Conference 1999 Conference Paper

On Minimum Edge Ranking Spanning Trees

  • Kazuhisa Makino
  • Yushi Uno
  • Toshihide Ibaraki

Abstract In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i. e. , find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case performance ratio \( \frac{{\min \{ (\Delta ^* - 1)\log n/\Delta ^*, \Delta ^* - 1\} }} {{\log (\Delta ^* + 1) - 1}} \), where n is the number of vertices in G and Δ * is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the analysis is based on novel properties of the edge ranking of trees.

Details
v2026.09.13