Author name cluster

Ryuhei Uehara

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.

20 papers

2 author rows

TCS Journal 2025 Journal Article

Gathering on a circle with limited visibility by anonymous oblivious robots

Giuseppe Antonio Di Luna
Ryuhei Uehara
Giovanni Viglietta
Yukiko Yamauchi

A swarm of anonymous oblivious mobile robots, operating in deterministic Look-Compute-Move cycles, is confined within a circular track. All robots agree on the clockwise direction (chirality), they are activated by an adversarial semi-synchronous scheduler (SSYNCH), and an active robot always reaches the destination point it computes (rigidity). Robots have limited visibility: each robot can see only the points on the circle that have an angular distance strictly smaller than a constant ϑ from the robot's current location, where 0 < ϑ ≤ π (angles are expressed in radians). We study the Gathering problem for such a swarm of robots: that is, all robots are initially in distinct locations on the circle, and their task is to reach the same point on the circle in a finite number of turns, regardless of the way they are activated by the scheduler. Note that, due to the anonymity of the robots, this task is impossible if the initial configuration is rotationally symmetric; hence, we have to make the assumption that the initial configuration be rotationally asymmetric. We prove that, if ϑ = π (i. e. , each robot can see the entire circle except its antipodal point), there is a distributed algorithm that solves the Gathering problem for swarms of any size. By contrast, we also prove that, if ϑ ≤ π / 2, no distributed algorithm solves the Gathering problem, regardless of the size of the swarm, even under the assumption that the initial configuration is rotationally asymmetric and the visibility graph of the robots is connected. The latter impossibility result relies on a probabilistic technique based on random perturbations, which is novel in the context of anonymous mobile robots. Such a technique is of independent interest, and immediately applies to other Pattern-Formation problems.

ECAI Conference 2025 Conference Paper

Multi-Objective Combinatorial Reconfiguration Considering Cost and Length by Answer Set Programming: Algorithms, Encodings, and Empirical Analysis

Kazuki Takada
Mutsunori Banbara
Takehiro Ito
Jun Kawahara
Shin-ichi Minato
Torsten Schaub
Ryuhei Uehara

We introduce the Multi-Objective Combinatorial Reconfiguration Optimization Problem (MO-CROP), and propose an Answer Set Programming (ASP) based approach for its solution. MO-CROP involves finding the Pareto-optimal sequences (or Pareto front) of adjacent feasible solutions between two given feasible solutions of a combinatorial problem, considering both cost and length. Our algorithm is compactly implemented through multi-shot ASP solving, and its implementing solver optirecon provides an effective tool for solving MO-CROP. As a concrete example of MO-CROP, we present an ASP encoding for solving the multi-objective independent set reconfiguration optimization problem. Experimental results on the benchmark set from the recent CoRe Challenge demonstrate our approach’s ability to capture diverse optimal sequences that reveal trade-offs between cost and length, a capability often lacking in traditional combinatorial reconfiguration methods.

TCS Journal 2024 Journal Article

Computational complexity of jumping block puzzles

Masaaki Kanzaki
Yota Otachi
Giovanni Viglietta
Ryuhei Uehara

In the context of computational complexity of puzzles, the sliding block puzzles play an important role. Depending on the rules and set of pieces, the sliding block puzzles can be polynomial-time solvable, NP-complete, or PSPACE-complete. On the other hand, a relatively new notion of jumping block puzzles has been proposed in the puzzle community. This is a counterpart to the token jumping model of the combinatorial reconfiguration problems in the context of block puzzles. We investigate some variants of jumping block puzzles, which are based on actual puzzles, and a natural model from the viewpoint of combinatorial reconfiguration, and determine their computational complexities. More precisely, we investigate two generalizations of two actual puzzles which are called Flip Over puzzles and Flying Block puzzles and one natural model of jumping block puzzles from the viewpoint of combinatorial reconfiguration. We prove that they are PSPACE-complete in general. We also prove the NP-completeness of these puzzles in some restricted cases, and we give polynomial-time algorithms for some restricted cases.

TCS Journal 2023 Journal Article

Mathematical characterizations and computational complexity of anti-slide puzzles

Ko Minamisawa
Ryuhei Uehara
Masao Hara

For a given set of pieces and a frame, an anti-slide puzzle asks us to arrange the pieces so that none of the pieces can slide in the frame. Since the first anti-slide puzzle that consists of dozens of cuboid pieces in 3D was invented, tons of anti-slide puzzles using pentominoes have been proposed. Some of them are not in a frame, which we call that interlock puzzles. In this paper, we investigate computational complexity of anti-slide puzzles and interlock puzzles in 2D. In previous work in theoretical computer science, a few models have been proposed for dealing with the notion of anti-slide, however, there exist gaps between these models and real puzzles. We first give mathematical characterizations of anti-slide puzzles and show the relationship between the previous work. Using a mathematical characterization, we give a polynomial time algorithm for determining if a given arrangement of polyominoes is anti-slide or not in a model. Next, we prove that the decision problem whether a given set of polyominoes can be arranged to be anti-slide or not is strongly NP-complete even if every piece is x-monotone. On the other hand, a set of pieces cannot be arranged to be interlocked if all pieces are convex polygons.

TCS Journal 2023 Journal Article

Sorting balls and water: Equivalence and computational complexity

Takehiro Ito
Jun Kawahara
Shin-ichi Minato
Yota Otachi
Toshiki Saitoh
Akira Suzuki
Ryuhei Uehara
Takeaki Uno

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps have gained popularity. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.

TCS Journal 2021 Journal Article

Shortest reconfiguration of sliding tokens on subclasses of interval graphs

Takeshi Yamada
Ryuhei Uehara

Suppose that two independent sets I b and I r of a graph such that | I b | = | I r | are given, and a token is placed on each vertex in I b. 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. The sliding token problem is one of the reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. Recently, the problems that aim at finding a shortest reconfiguration sequence are investigated. In general, even if it is polynomial time solvable to decide whether two instances are reconfigurable into each other, it can be NP-hard to find a shortest sequence between them. In this paper, we show that the problem for finding a shortest sequence between two independent sets is polynomial time solvable for some graph classes which are subclasses of the class of interval graphs. As far as the authors know, this is the first polynomial time algorithm for the shortest sliding token problem for a graph class that requires detours.

TCS Journal 2020 Journal Article

Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs

Kazuaki Yamazaki
Toshiki Saitoh
Masashi Kiyomi
Ryuhei Uehara

In this paper, a general framework for enumerating every element in a graph class is given. The main feature of this framework is that it is designed to enumerate only nonisomorphic graphs in a graph class. Applying this framework to the classes of interval graphs and permutation graphs, we give efficient enumeration algorithms for these graph classes such that each element in the class is output in a polynomial time delay. The experimental results are also given. The catalogs of graphs in these graph classes are also provided.

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.

TCS Journal 2015 Journal Article

Linear-time algorithm for sliding tokens on trees

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

Suppose that we are given two independent sets I b and I r of a graph such that | I b | = | I r |, 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.

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.

TCS Journal 2014 Journal Article

Base-object location problems for base-monotone regions

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

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 base-lines (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 × 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.

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.

TCS Journal 2013 Journal Article

The complexity of the stamp folding problem

Takuya Umesato
Toshiki Saitoh
Ryuhei Uehara
Hiro Ito
Yoshio Okamoto

There are many folded states consistent with a given mountain–valley pattern of equidistant creases on a long paper strip. We would like to fold a paper strip such that the number of paper layers between each pair of hinged paper segments, called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem: minimization of the maximum crease width, and minimization of the total crease width. This optimization problem was recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in O ( ( k + 1 ) k n ) time where n is the number of creases and k is the total crease width.

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.

TCS Journal 2010 Journal Article

Efficient enumeration of all ladder lotteries and its application

Katsuhisa Yamanaka
Shin-ichi Nakano
Yasuko Matsui
Ryuhei Uehara
Kento Nakada

A ladder lottery, known as “Amidakuji” in Japan, is a common way to choose a permutation randomly. A ladder lottery L corresponding to a given permutation π is optimal if L has the minimum number of horizontal lines among the ladder lotteries corresponding to π. In this paper we show that for any two optimal ladder lotteries L 1 and L 2 of a permutation, there exists a sequence of local modifications which transforms L 1 into L 2. We also give an algorithm to enumerate all optimal ladder lotteries of a given permutation. By setting π = ( n, n − 1, …, 1 ), the algorithm enumerates all arrangements of n pseudolines efficiently. By implementing the algorithm we compute the number of arrangements of n pseudolines for each n ≤ 11.

TCS Journal 2010 Journal Article

Enumeration of the perfect sequences of a chordal graph

Yasuko Matsui
Ryuhei Uehara
Takeaki Uno

A graph is chordal if and only if it has no chordless cycle of length more than three. The set of maximal cliques in a chordal graph admits special tree structures called clique trees. A perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. This paper addresses the problem of enumerating all the perfect sequences. Although this problem has statistical applications, no efficient algorithm has been proposed. There are two difficulties with developing this type of algorithm. First, a chordal graph does not generally have a unique clique tree. Second, a perfect sequence can normally be generated by two or more distinct clique trees. Thus it is hard using a straightforward algorithm to generate perfect sequences from each possible clique tree. In this paper, we propose a method to enumerate perfect sequences without constructing clique trees. As a result, we have developed the first polynomial delay algorithm for dealing with this problem. In particular, the time complexity of the algorithm on average is O ( 1 ) for each perfect sequence.

TCS Journal 2010 Journal Article

Reconstruction of interval graphs

Masashi Kiyomi
Toshiki Saitoh
Ryuhei Uehara

The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems by limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs.

TCS Journal 2009 Journal Article

Scale free interval graphs

Naoto Miyoshi
Takeya Shigezumi
Ryuhei Uehara
Osamu Watanabe

Scale free graphs have attracted attention by their non-uniform structure that can be used as a model for various social and physical networks. In this paper, we propose a natural and simple random model for generating scale free interval graphs. The model generates a set of intervals randomly under a certain distribution, which defines a random interval graph. The main advantage of the model is its simpleness. The structure/properties of generated graphs are analyzable by relatively simple probabilistic and/or combinatorial arguments, which is different from many other models. Based on such arguments, we show for our random interval graph that its degree distribution follows a power law, and that it has a large average clustering coefficient.

TCS Journal 2000 Journal Article

Identification of partial disjunction, parity, and threshold functions

Ryuhei Uehara
Kensei Tsuchida
Ingo Wegener

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.

TCS Journal 1999 Journal Article

Fast RNC and NC algorithms for maximal path sets

Ryuhei Uehara
Zhi-Zhong Chen
Xin He

We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. One is randomized and runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The other is deterministic and runs in O(log 2 n) time with O( Δ2(n + m) log n ) processors on an EREW PRAM. The results improve on the previous bests and can also be extended to digraphs. We then use the results to improve the time complexity of the best previous NC approximation algorithm for the shortest superstring problem.