Arrow Research search

Author name cluster

Yota Otachi

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.

26 papers
2 author rows

Possible papers

26

MFCS Conference 2025 Conference Paper

Broadcasting Under Structural Restrictions

  • Yudai Egami
  • Tatsuya Gima
  • Tesshu Hanaka
  • Yasuaki Kobayashi
  • Michael Lampis
  • Valia Mitsou
  • Edouard Nemery
  • Yota Otachi

In the Telephone Broadcast problem we are given a graph G = (V, E) with a designated source vertex s ∈ V. Our goal is to transmit a message, which is initially known only to s, to all vertices of the graph by using a process where in each round an informed vertex may transmit the message to one of its uninformed neighbors. The optimization objective is to minimize the number of rounds. Following up on several recent works, we investigate the structurally parameterized complexity of Telephone Broadcast. In particular, we first strengthen existing NP-hardness results by showing that the problem remains NP-complete on graphs of bounded tree-depth and also on cactus graphs which are one vertex deletion away from being path forests. Motivated by this (severe) hardness, we study several other parameterizations of the problem and obtain FPT algorithms parameterized by vertex integrity (generalizing a recent FPT algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach [TCS 2024]) and by distance to clique, as well as FPT approximation algorithms parameterized by clique-cover and cluster vertex deletion. Furthermore, we obtain structural results that relate the length of the optimal broadcast protocol of a graph G with its pathwidth and tree-depth. By presenting a substantial improvement over the best previously known bound for pathwidth (Aminian, Kamali, Seyed-Javadi, and Sumedha [ICALP 2025]) we exponentially improve the approximation ratio achievable in polynomial time on graphs of bounded pathwidth from 𝒪(4^pw) to 𝒪(pw).

Details

TCS Journal 2025 Journal Article

Dichotomies for tree minor containment with structural parameters

  • Tatsuya Gima
  • Soh Kumabe
  • Kazuhiro Kurita
  • Yuto Okada
  • Yota Otachi

The problem of determining whether a graph G contains another graph H as a minor, referred to as the minor containment problem, is a fundamental problem in the field of graph algorithms. While the problem is NP -complete in general, it can be tractable on some restricted graph classes. This study focuses on the case where both G and H are trees, known as the tree minor containment problem. Even in this case, the problem is known to be NP -complete. In contrast, polynomial-time algorithms are known for the case when both trees are caterpillars or when the maximum degree of H is a constant. Our research aims to clarify the boundary of tractability and intractability for the tree minor containment problem. Specifically, we provide complexity dichotomies for the problem based on three structural parameters: diameter, pathwidth, and path eccentricity.

Details DOI

TCS Journal 2025 Journal Article

On the complexity of list H -packing for sparse graph classes

  • Tatsuya Gima
  • Tesshu Hanaka
  • Yasuaki Kobayashi
  • Yota Otachi
  • Tomohito Shirai
  • Akira Suzuki
  • Yuma Tamura
  • Xiao Zhou

The problem of packing as many subgraphs isomorphic to some H ∈ H as possible into a graph, where H is a collection of graphs, has been well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider “list variants” of these problems: Given a graph G, an integer k, and a collection L H of subgraphs of G isomorphic to some H ∈ H, the goal is to compute k subgraphs in L H that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.

Details DOI

MFCS Conference 2025 Conference Paper

Parameterized Spanning Tree Congestion

  • Michael Lampis
  • Valia Mitsou
  • Edouard Nemery
  • Yota Otachi
  • Manolis Vasilakis
  • Daniel Vaz 0001

In this paper we study the Spanning Tree Congestion problem, where we are given an undirected graph G = (V, E) and are asked to find a spanning tree T of minimum maximum congestion. Here, the congestion of an edge e ∈ T is the number of edges uv ∈ E such that the (unique) path from u to v in T traverses e. We consider this well-studied NP-hard problem from the point of view of (structural) parameterized complexity and obtain the following results: - We resolve a natural open problem by showing that Spanning Tree Congestion is not FPT parameterized by treewidth (under standard assumptions). More strongly, we present a generic reduction which applies to (almost) any parameter of the form "vertex-deletion distance to class 𝒞", thus obtaining W[1]-hardness for more restricted parameters, including tree-depth plus feedback vertex set, or incomparable to treewidth, such as twin cover. Via a slight tweak of the same reduction we also show that the problem is NP-complete on graphs of modular-width 4. - Even though it is known that Spanning Tree Congestion remains NP-hard on instances with only one vertex of unbounded degree, it is currently open whether the problem remains hard on bounded-degree graphs. We resolve this question by showing NP-hardness on graphs of maximum degree 8. - Complementing the problem’s W[1]-hardness for treewidth, we formulate an algorithm that runs in time roughly {(k+w)}^{𝒪(w)}, where k is the desired congestion and w the treewidth, improving a previous argument for parameter k+w that was based on Courcelle’s theorem. This explicit algorithm pays off in two ways: it allows us to obtain an FPT approximation scheme for parameter treewidth, that is, a (1+ε)-approximation running in time roughly {(w/ε)}^{𝒪(w)}; and it leads to an exact FPT algorithm for parameter clique-width+k via a Win/Win argument. - Finally, motivated by the problem’s hardness for most standard structural parameters, we present FPT algorithms for several more restricted cases, namely, for the parameters vertex-deletion distance to clique; vertex integrity; and feedback edge set, in the latter case also achieving a single-exponential running time dependence on the parameter.

Details

TCS Journal 2025 Journal Article

Structural parameterizations of vertex integrity

  • Tatsuya Gima
  • Tesshu Hanaka
  • Yasuaki Kobayashi
  • Ryota Murai
  • Hirotaka Ono
  • Yota Otachi

The graph parameter vertex integrity measures how vulnerable a graph is to a removal of a small number of vertices. More precisely, a graph with small vertex integrity admits a small number of vertex removals to make the remaining connected components small. In this paper, we initiate a systematic study of structural parameterizations of the problem of computing the unweighted/weighted vertex integrity. As structural graph parameters, we consider well-known parameters such as clique-width, treewidth, pathwidth, treedepth, modular-width, neighborhood diversity, twin cover number, and cluster vertex deletion number. We show several positive and negative results and present sharp complexity contrasts. We also show that the vertex integrity can be approximated within an O ( log ⁡ opt ) factor.

Details DOI

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.

Details DOI

TCS Journal 2024 Journal Article

Grouped domination parameterized by vertex cover, twin cover, and beyond

  • Tesshu Hanaka
  • Hirotaka Ono
  • Yota Otachi
  • Saeki Uda

A dominating set S of graph G is called an r-grouped dominating set if S can be partitioned into S 1, S 2, …, S k such that the size of each unit S i is r and the subgraph of G induced by S i is connected. The concept of r-grouped dominating sets generalizes several well-studied variants of dominating sets with requirements for connected component sizes, such as the ordinary dominating sets ( r = 1 ), paired dominating sets ( r = 2 ), and connected dominating sets (r is arbitrary and k = 1 ). In this paper, we investigate the computational complexity of r -Grouped Dominating Set, which is the problem of deciding whether a given graph has an r-grouped dominating set with at most k units. For general r, r -Grouped Dominating Set is hard to solve in various senses because the hardness of the connected dominating set is inherited. We thus focus on the case in which r is a constant or a parameter, but we see that r -Grouped Dominating Set for every fixed r > 0 is still hard to solve. From the observations about the hardness, we consider the parameterized complexity concerning well-studied graph structural parameters. We first see that r -Grouped Dominating Set is fixed-parameter tractable for r and treewidth, which is derived from the fact that the condition of r-grouped domination for a constant r can be represented as monadic second-order logic ( MSO 2 ). This fixed-parameter tractability is good news, but the running time is not practical. We then design an O ⁎ ( min ⁡ { ( 2 τ ( r + 1 ) ) τ, ( 2 τ ) 2 τ } ) -time algorithm for general r ≥ 2, where τ is the twin cover number, which is a parameter between vertex cover number and clique-width. For paired dominating set and trio dominating set, i. e. , r ∈ { 2, 3 }, we can speed up the algorithm, whose running time becomes O ⁎ ( ( r + 1 ) τ ). We further argue the relationship between FPT results and graph parameters, which draws the parameterized complexity landscape of r -Grouped Dominating Set.

Details DOI

AAAI Conference 2023 Conference Paper

A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems

  • Tesshu Hanaka
  • Masashi Kiyomi
  • Yasuaki Kobayashi
  • Yusuke Kobayashi
  • Kazuhiro Kurita
  • Yota Otachi

Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world problems as objective functions and constraints are only ``approximately'' formulated for original real-world problems. To solve this issue, finding \emph{multiple} solutions is a natural direction, and diversity of solutions is an important concept in this context. Unfortunately, finding diverse solutions is much harder than finding a single solution. To cope with the difficulty, we investigate the approximability of finding diverse solutions. As a main result, we propose a framework to design approximation algorithms for finding diverse solutions, which yields several outcomes including constant-factor approximation algorithms for finding diverse matchings in graphs and diverse common bases in two matroids and PTASes for finding diverse minimum cuts and interval schedulings.

PDF Details DOI

TCS Journal 2023 Journal Article

Reconfiguring (non-spanning) arborescences

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

In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring arborescences in a digraph, where an arborescence is a directed graph such that its underlying undirected graph forms a tree and all vertices have in-degree at most 1. Given two arborescences in a digraph, the goal of the problem is to determine whether there is a (reconfiguration) sequence of arborescences between the given arborescences such that each arborescence in the sequence can be obtained from the previous one by removing an arc and then adding another arc. We show that this problem can be solved in polynomial time, whereas the problem is PSPACE-complete when we restrict arborescences in a reconfiguration sequence to directed paths or relax to directed acyclic graphs. We also show that there is a polynomial-time algorithm for finding a shortest reconfiguration sequence between two spanning arborescences.

Details DOI

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

AAAI Conference 2022 Conference Paper

Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study

  • Tesshu Hanaka
  • Yasuaki Kobayashi
  • Kazuhiro Kurita
  • See Woo Lee
  • Yota Otachi

Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study the following type of problems: given an integer k, the problem asks for k solutions such that the sum of pairwise (weighted) Hamming distances between these solutions is maximized. Such solutions are called diverse solutions. We present a polynomial-time algorithm for finding diverse shortest stpaths in weighted directed graphs. Moreover, we study the diverse version of other classical combinatorial problems such as diverse weighted matroid bases, diverse weighted arborescences, and diverse bipartite matchings. We show that these problems can be solved in polynomial time as well. To evaluate the practical performance of our algorithm for finding diverse shortest st-paths, we conduct a computational experiment with synthetic and real-world instances. The experiment shows that our algorithm successfully computes diverse solutions within reasonable computational time.

PDF Details

TCS Journal 2022 Journal Article

Exploring the gap between treedepth and vertex cover through vertex integrity

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

For problems intractable on graphs of bounded treewidth, two graph parameters treedepth and vertex cover number have been used to obtain fine-grained algorithmic and complexity results. Although the studies in this direction are successful, we still need a systematic way for further investigations because the graphs of bounded vertex cover number form a rather small subclass of graphs of bounded treedepth. To fill this gap, we use another graph parameter, vertex integrity, which is placed between the two parameters mentioned above. For several graph problems, we generalize fixed-parameter tractability results parameterized by vertex cover number to the ones parameterized by vertex integrity. We also show some finer complexity contrasts by showing hardness with respect to vertex integrity or treedepth.

Details DOI

MFCS Conference 2022 Conference Paper

Independent Set Reconfiguration on Directed Graphs

  • Takehiro Ito
  • Yuni Iwamasa
  • Yasuaki Kobayashi
  • Yu Nakahata
  • Yota Otachi
  • Masahiro Takahashi
  • Kunihiro Wasa

Directed Token Sliding asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a local operation that exchanges a vertex in the current set with one of its out-neighbors, while keeping the nonadjacency. It can be seen as a reconfiguration process where a token is placed on each vertex in the current set, and the local operation slides a token along an arc respecting its direction. Previously, such a problem was extensively studied on undirected graphs, where the edges have no directions and thus the local operation is symmetric. Directed Token Sliding is a generalization of its undirected variant since an undirected edge can be simulated by two arcs of opposite directions. In this paper, we initiate the algorithmic study of Directed Token Sliding. We first observe that the problem is PSPACE-complete even if we forbid parallel arcs in opposite directions and that the problem on directed acyclic graphs is NP-complete and W[1]-hard parameterized by the size of the sets in consideration. We then show our main result: a linear-time algorithm for the problem on directed graphs whose underlying undirected graphs are trees, which are called polytrees. Such a result is also known for the undirected variant of the problem on trees [Demaine et al. TCS 2015], but the techniques used here are quite different because of the asymmetric nature of the directed problem. We present a characterization of yes-instances based on the existence of a certain set of directed paths, and then derive simple equivalent conditions from it by some observations, which yield an efficient algorithm. For the polytree case, we also present a quadratic-time algorithm that outputs, if the input is a yes-instance, one of the shortest reconfiguration sequences.

Details

MFCS Conference 2022 Conference Paper

Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets

  • Ankit Abhinav
  • Susobhan Bandopadhyay
  • Aritra Banik
  • Yasuaki Kobayashi
  • Shunsuke Nagano
  • Yota Otachi
  • Saket Saurabh 0001

For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path is a path P between s and t such that the set of vertices of P does not separate G, that is, G - V(P) is connected. An s-t path P is non-disconnecting if G - E(P) is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating s-t path of length at most k is W[1]-hard parameterized by k, while the non-disconnecting counterpart is fixed-parameter tractable (FPT) parameterized by k. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is FPT parameterized by k on planar graphs and on unit disk graphs (where no s, t is given). Further, we give a polynomial-time algorithm on chordal graphs if k is the distance of the shortest path between s and t.

Details

AAAI Conference 2021 Conference Paper

Finding Diverse Trees, Paths, and More

  • Tesshu Hanaka
  • Yasuaki Kobayashi
  • Kazuhiro Kurita
  • Yota Otachi

Mathematical modeling is a standard approach to solve many real-world problems and diversity of solutions is an important issue, emerging in applying solutions obtained from mathematical models to real-world problems. Many studies have been devoted to finding diverse solutions. Baste et al. (Algorithms 2019, IJCAI 2020) recently initiated the study of computing diverse solutions of combinatorial problems from the perspective of fixed-parameter tractability. They considered problems of finding r solutions that maximize some diversity measures (the minimum or sum of the pairwise Hamming distances among them) and gave some fixed-parameter tractable algorithms for the diverse version of several well-known problems, such as VERTEX COVER, FEEDBACK VERTEX SET, d-HITTING SET, and problems on bounded-treewidth graphs. In this work, we further investigate the (fixed-parameter) tractability of problems of finding diverse spanning trees, paths, and several subgraphs. In particular, we show that, given a graph G and an integer r, the problem of computing r spanning trees of G maximizing the sum of the pairwise Hamming distances among them can be solved in polynomial time. To the best of the authors’ knowledge, this is the first polynomial-time solvable case for finding diverse solutions of unbounded size.

PDF Details

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

TCS Journal 2019 Journal Article

On structural parameterizations of firefighting

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

The Firefighting problem is defined as follows. At time t = 0, a fire breaks out at a vertex of a graph. At each time step t ≥ 1, a firefighter permanently defends (protects) an unburned vertex, and the fire then spreads to all undefended neighbors from the vertices on fire. This process stops when the fire cannot spread anymore. The goal is to find a sequence of vertices for the firefighter that maximizes the number of saved (non burned) vertices. The Firefighting problem turns out to be NP -hard even when restricted to bipartite graphs or trees of maximum degree three. We study the parameterized complexity of the Firefighting problem for various structural parameterizations. All our parameters measure the distance to a graph class (in terms of vertex deletion) on which the Firefighting problem admits a polynomial-time algorithm. To begin with, we show that the problem is W [ 1 ] -hard when parameterized by the size of a modulator to diameter at most two graphs and split graphs. In contrast to the above intractability results, we show that Firefighting is fixed parameter tractable ( FPT ) when parameterized by the size of a modulator to cographs, threshold graphs and disjoint unions of stars. We further investigate the kernelization complexity of the problem and show that it does not admit a polynomial kernel when parameterized by the size of a modulator to a disjoint union of stars under some complexity-theoretic assumptions.

Details DOI

TCS Journal 2019 Journal Article

Reconfiguration of colorable sets in classes of perfect graphs

  • Takehiro Ito
  • Yota Otachi

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 (called a reconfiguration sequence) 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.

Details DOI

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

Vertex deletion problems on chordal graphs

  • Yixin Cao
  • Yuping Ke
  • Yota Otachi
  • Jie You

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.

Details DOI

TCS Journal 2015 Journal Article

Extending partial representations of subclasses of chordal graphs

  • Pavel Klavík
  • Jan Kratochvíl
  • Yota Otachi
  • Toshiki Saitoh

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.

Details DOI

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.

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

Efficient algorithms for network localization using cores of underlying graphs

  • Meng Li
  • Yota Otachi
  • Takeshi Tokuyama

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.

Details DOI

TCS Journal 2012 Journal Article

Efficient enumeration of ordered trees with k leaves

  • Katsuhisa Yamanaka
  • Yota Otachi
  • Shin-ichi Nakano

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.

Details DOI
v2026.09.13