Author name cluster

Takeaki 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.

14 papers

2 author rows

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.

Details DOI

TCS Journal 2021 Journal Article

A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

Kazuhiro Kurita
Kunihiro Wasa
Takeaki Uno
Hiroki Arimura

In this study, we address the independent set enumeration problem. Although several efficient enumeration algorithms and careful analyses have been proposed for maximal independent sets, no fine-grained analysis has been given for the non-maximal variant. As the main result, we propose an enumeration algorithm for the non-maximal variant that runs in O ( q ) amortized time and linear space, where q is the clique number, i. e. , the maximum size of a clique in an input graph. Note that the proposed algorithm works correctly even if the exact value of q is unknown. It is optimal for graphs with a bounded clique number, such as, triangle-free graphs, bipartite graphs, planar graphs, bounded degenerate graphs, nowhere dense graphs, and F-free graphs for any fixed graph F, where a F-free graph is a graph that has no copy of F as a subgraph. Furthermore, with a slight modification of our proposed algorithm, we can enumerate independent sets with the size at most k in the same time and space complexity. This problem is a generalization of the original problem since this is equal to the original problem if k = n.

Details DOI

TCS Journal 2020 Journal Article

Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph

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

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 ⋅ ω ( G ) ) for any n-vertex chordal graph with m edges, where ω ( G ) ≤ n is the maximum size of a clique in G. Degeneracy is a well known sparsity measure, and k-degenerate subgraphs are a notion of sparse subgraphs, which generalizes other problems such as independent sets (0-degenerate subgraphs) and forests (1-degenerate subgraphs). Many efficient enumeration algorithms are designed by solving the so-called Extension problem, which asks whether there exists a maximal solution containing a given set of nodes, but no node from a forbidden set. We show that solving this problem is np-complete for maximal k-degenerate induced subgraphs, motivating the need for additional techniques.

Details DOI

MFCS Conference 2019 Conference Paper

Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs

Alessio Conte
Roberto Grossi
Mamadou Moustapha Kanté
Andrea Marino 0001
Takeaki Uno
Kunihiro Wasa

This paper investigates induced Steiner subgraphs as a variant of the classical Steiner trees, so as to compactly represent the (exponentially many) Steiner trees sharing the same underlying induced subgraph. We prove that the enumeration of all (inclusion-minimal) induced Steiner subgraphs is harder than the well-known Hypergraph Transversal enumeration problem if the number of terminals is not fixed. When the number of terminals is fixed, we propose a polynomial delay algorithm for listing all induced Steiner subgraphs of minimum size. We also propose a polynomial delay algorithm for listing the set of minimal induced Steiner subgraphs when the number of terminals is 3.

Details

STOC Conference 2019 Conference Paper

New polynomial delay bounds for maximal subgraph enumeration by proximity search

Alessio Conte
Takeaki Uno

In this paper we propose polynomial delay algorithms for several maximal subgraph listing problems, by means of a seemingly novel technique which we call proximity search. Our result involves modeling the space of solutions as an implicit directed graph called “solution graph”, a method common to other enumeration paradigms such as reverse search. Such methods, however, can become inefficient due to this graph having vertices with high (potentially exponential) degree. The novelty of our algorithm consists in providing a technique for generating better solution graphs, reducing the out-degree of its vertices with respect to existing approaches, and proving that it remains strongly connected. Applying this technique, we obtain polynomial delay listing algorithms for several problems for which output-sensitive results were, to the best of our knowledge, not known. These include Maximal Bipartite Subgraphs, Maximal k -Degenerate Subgraphs (for bounded k ), Maximal Induced Chordal Subgraphs, and Maximal Induced Trees. We present these algorithms, and give insight on how this general technique can be applied to other problems.

Details

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

IROS Conference 2015 Conference Paper

Map merging using cycle consistency check and RANSAC-based spanning tree selection

Masahiro Tomono
Takeaki Uno

This paper proposes a method of map merging using cycle consistency check and spanning tree selection by RANSAC. Key issues in map merging are the transformation of the coordinate frame of each submap to a global coordinate frame and the rejection of outliers (false arcs) in a pose graph. The proposed method reduces outliers using cycle consistency constraints. To cope with the exponential increase of cycles, cycle consistency check is applied iteratively with a limited number of chordless cycles. Then, spanning trees having only inlier arcs are selected by RANSAC to find the transformation of each submap to a global coordinate frame. Experiments using public datasets show that the proposed method successfully obtained good spanning trees at high outlier ratio.

Details

TCS Journal 2015 Journal Article

Swapping labeled tokens on graphs

Katsuhisa Yamanaka
Erik D. Demaine
Takehiro Ito
Jun Kawahara
Masashi Kiyomi
Yoshio Okamoto
Toshiki Saitoh
Akira Suzuki

Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O ( n 2 ) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.

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

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.

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 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.

Details DOI

TCS Journal 2010 Journal Article

On listing, sampling, and counting the chordal graphs with edge constraints

Shuji Kijima
Masashi Kiyomi
Yoshio Okamoto
Takeaki Uno

We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume that at least one of the input graphs is chordal. The setting is a natural generalization of chordal completions and deletions. For the listing problem, we give an efficient algorithm running in polynomial time per output with polynomial space. As for the sampling problem, we give two clues that indicate that a random sampling is not easy. The first clue is that we show #P-completeness results for counting problems. The second clue is that we give an instance for which a natural Markov chain suffers from an exponential mixing time. These results provide a unified viewpoint from algorithms’ theory to problems arising from various areas such as statistics, data mining, and numerical computation.

Details DOI

IJCAI Conference 2005 Conference Paper

Generalized Amazons is PSPACE-Complete

Timothy Furtak
Masashi Kiyomi
Takeaki Uno
Michael

Amazons is a perfect information board game with simple rules and large branching factors. Two players alternately move chess queen-like pieces and block squares on a 10×10 playing field. The player who makes the last move wins. Amazons endgames usually decompose into independent subgames. Therefore, the game is a natural testbed for combinatorial game theory. It was known that determining the winner of simple generalized Amazons endgames is NP-equivalent. This paper presents two proofs for the PSPACEcompleteness of the generalized version of the full game.

PDF