Takehiro Ito

TCS Journal 2026 Journal Article

Independent set reconfiguration under bounded-hop token jumping

• Hiroki Hatano
• Naoki Kitamura
• Taisuke Izumi
• Takehiro Ito
• Toshimitsu Masuzawa

The independent set reconfiguration problem (ISReconf) is the problem of determining, for two given independent sets of a graph, whether one can be transformed into the other by repeatedly applying a prescribed reconfiguration rule. There are two well-studied reconfiguration rules, called the Token Sliding (TS) rule and the Token Jumping (TJ) rule, and it is known that the complexity status of ISReconf differs between the TS and TJ rules for some graph classes. In this paper, we analyze how changes in reconfiguration rules affect the computational complexity of ISReconf. To this end, we generalize the TS and TJ rules to a unified reconfiguration rule, called the k-Jump rule, which removes one vertex from a current independent set and adds a vertex within distance k from the removed vertex to obtain another independent set having the same cardinality. We give the following three results: First, we show that the reconfigurability of any ISReconf instance does not change for all k ≥ 3. Second, we present a polynomial-time algorithm to solve ISReconf under the 2-Jump rule for split graphs. Third, we consider the shortest variant of ISReconf, which determines whether there is a transformation of at most ℓ steps, for a given integer ℓ ≥ 0. We prove that this shortest variant under the k-Jump rule is NP-complete for chordal graphs of diameter at most 2 k + 1, for any k ≥ 3.

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.

SoCS Conference 2024 Conference Paper

CoRe Challenge 2022/2023: Empirical Evaluations for Independent Set Reconfiguration Problems (Extended Abstract)

• Takehide Soh
• Tomoya Tanjo
• Yoshio Okamoto
• Takehiro Ito

In this extended abstract, we describe CoRe Challenge 2022/2023, an international competition series aiming to construct the technical foundation of practical research for Combinatorial Reconfiguration. This competition series targets one of the most well-studied reconfiguration problems, called the independent set reconfiguration problem under the token jumping model, which asks a step-by-step transformation between two given independent sets in a graph. Theoretically, the problem is PSPACE-complete, which implies that there exist instances such that even a shortest transformation requires super-polynomial steps with respect to the input size under the assumption of $NP \neq PSPACE$. The competition series consists of four tracks: three tracks take two independent sets of a graph as input, and ask the existence of a transformation, a shortest transformation, a longest transformation between them; and the last track takes only a number of vertices as input, and asks for an instance of the specified number of vertices that needs a longer shortest transformation steps. We describe the background of the competition series and highlight the results of the solver and graph tracks.

TCS Journal 2023 Journal Article

Fixed-parameter algorithms for graph constraint logic

• Tatsuhiko Hatanaka
• Felix Hommelsheim
• Takehiro Ito
• Yusuke Kobayashi
• Moritz Mühlenthaler
• Akira Suzuki

Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures PSPACE and has been a useful tool for proving algorithmic hardness of many puzzles, games, and reconfiguration problems. In particular, its usefulness stems from the fact that it remains PSPACE-complete even under severe restrictions of the weights (e. g. , only edge-weights one and two are needed) and the structure of the constraint graph (e. g. , planar and/or graphs of bounded bandwidth). While such restrictions on the structure of constraint graphs do not seem to limit the expressiveness of NCL, the building blocks of the constraint graphs cannot be limited without losing expressiveness: We consider as parameters the number of weight-one edges and the number of weight-two edges of a constraint graph, as well as the number of and or or vertices of an and/or constraint graph. We show that NCL is fixed-parameter tractable (FPT) for any of these parameters. In particular, for NCL parameterized by the number of weight-one edges or the number of and vertices, we obtain a linear kernel. It follows that, in a sense, NCL as introduced by Hearn and Demaine is defined in the most economical way for the purpose of capturing PSPACE.

TCS Journal 2023 Journal Article

On reachable assignments under dichotomous preferences

• Takehiro Ito
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yuta Nozaki
• Yoshio Okamoto
• Kenta Ozeki

We consider the problem of determining whether a target item assignment can be reached from an initial item assignment by a sequence of pairwise exchanges of items between agents. In particular, we consider the situation where each agent has a dichotomous preference over the items, that is, each agent evaluates each item as acceptable or unacceptable. Furthermore, we assume that communication between agents is limited, and the relationship is represented by an undirected graph. Then, a pair of agents can exchange their items only if they are connected by an edge and the involved items are acceptable. We prove that this problem is PSPACE -complete even when the communication graph is complete (that is, every pair of agents can exchange their items), and this problem can be solved in polynomial time if an input graph is a tree.

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.

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.

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.

SODA Conference 2022 Conference Paper

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

• Takehiro Ito
• Yuni Iwamasa
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi 0001
• Shun-ichi Maezawa
• Yuta Nozaki
• Yoshio Okamoto

We initiate the study of k -edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2 k -edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge-connectivity, and the final orientation is k -edge-connected. This yields an “edge-flip based” new proof of Nash-Williams' theorem: an undirected graph G has a k -edge-connected orientation if and only if G is 2 k -edge-connected. As another consequence of the theorem, we prove that the edge-flip graph of k -edge-connected orientations of an undirected graph G is connected if G is (2 k + 2)-edge-connected. This has been known to be true only when k = 1.

AAAI Conference 2022 Conference Paper

Reforming an Envy-Free Matching

• Takehiro Ito
• Yuni Iwamasa
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yuta Nozaki
• Yoshio Okamoto
• Kenta Ozeki

We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.

TCS Journal 2021 Journal Article

Algorithms for gerrymandering over graphs

• Takehiro Ito
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yoshio Okamoto

We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP-complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two.

TCS Journal 2021 Journal Article

Approximability of the independent feedback vertex set problem for bipartite graphs

• Yuma Tamura
• Takehiro Ito
• Xiao Zhou

Given an undirected graph G with n vertices, the independent feedback vertex set problem is to find a vertex subset F of G with the minimum number of vertices such that F is both an independent set and a feedback vertex set of G, if it exists. This problem is known to be NP-hard for bipartite planar graphs of maximum degree four. In this paper, we study the approximability of the problem. We first show that, for any fixed ε > 0, unless P = NP, there exists no polynomial-time n 1 − ε -approximation algorithm even for bipartite planar graphs. We then give an α ( Δ − 1 ) / 2 -approximation algorithm for bipartite graphs G of maximum degree Δ, which runs in t ( α, G ) + O ( Δ n ) time, under the assumption that there is an α-approximation algorithm for the original feedback vertex set problem on bipartite graphs which runs in t ( α, G ) time. This algorithmic result also yields a polynomial-time (exact) algorithm for the independent feedback vertex set problem on bipartite graphs of maximum degree three.

TCS Journal 2020 Journal Article

Complexity of the multi-service center problem

• Takehiro Ito
• Naonori Kakimura
• Yusuke Kobayashi

The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars.

TCS Journal 2020 Journal Article

Diameter of colorings under Kempe changes

• Marthe Bonamy
• Marc Heinrich
• Takehiro Ito
• Yusuke Kobayashi
• Haruka Mizuta
• Moritz Mühlenthaler
• Akira Suzuki
• Kunihiro Wasa

Given a k-coloring of a graph G, a Kempe-change for two colors a and b produces another k-coloring of G, as follows: first choose a connected component in the subgraph of G induced by the two color classes of a and b, and then swap the colors a and b in the component. Two k-colorings are called Kempe-equivalent if one can be transformed into the other by a sequence of Kempe-changes. We consider two problems, defined as follows: First, given two k-colorings of a graph G, Kempe Reachability asks whether they are Kempe-equivalent; and second, given a graph G and a positive integer k, Kempe Connectivity asks whether any two k-colorings of G are Kempe-equivalent. We analyze the complexity of these problems from the viewpoint of graph classes. We prove that Kempe Reachability is PSPACE -complete for any fixed k ≥ 3, and that it remains PSPACE -complete even when restricted to three colors and planar graphs of maximum degree six. Furthermore, we show that both problems admit polynomial-time algorithms on chordal graphs, bipartite graphs, and cographs. For each of these graph classes, we give a non-trivial upper bound on the number of Kempe-changes needed in order to certify that two k-colorings are Kempe-equivalent.

TCS Journal 2020 Journal Article

Reconfiguring spanning and induced subgraphs

• Tesshu Hanaka
• Takehiro Ito
• Haruka Mizuta
• Benjamin Moore
• Naomi Nishimura
• Vijay Subramanya
• Akira Suzuki
• Krishna Vaidyanathan

Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as subgraph reconfiguration, most of the related results appear under the name of the property under consideration; for example, independent set, clique, and matching. In this paper, we systematically clarify the complexity status of subgraph reconfiguration with respect to graph structure properties.

AAMAS Conference 2019 Conference Paper

Algorithms for Gerrymandering over Graphs

• Takehiro Ito
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yoshio Okamoto

We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP-complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two.

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.

MFCS Conference 2019 Conference Paper

Reconfiguration of Minimum Steiner Trees via Vertex Exchanges

• Haruka Mizuta
• Tatsuhiko Hatanaka
• Takehiro Ito
• Xiao Zhou 0001

In this paper, we study the problem of deciding if there is a transformation between two given minimum Steiner trees of an unweighted graph such that each transformation step respects a prescribed reconfiguration rule and results in another minimum Steiner tree of the graph. We consider two reconfiguration rules, both of which exchange a single vertex at a time, and generalize the known reconfiguration problem for shortest paths in an unweighted graph. This generalization implies that our problems under both reconfiguration rules are PSPACE-complete for bipartite graphs. We thus study the problems with respect to graph classes, and give some boundaries between the polynomial-time solvable and PSPACE-complete cases.

MFCS Conference 2019 Conference Paper

The Perfect Matching Reconfiguration Problem

• Marthe Bonamy
• Nicolas Bousquet 0001
• Marc Heinrich
• Takehiro Ito
• Yusuke Kobayashi 0001
• Arnaud Mary
• Moritz Mühlenthaler
• Kunihiro Wasa

We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as P_4-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.

TCS Journal 2018 Journal Article

Parameterized complexity of the list coloring reconfiguration problem with graph parameters

• Tatsuhiko Hatanaka
• Takehiro Ito
• Xiao Zhou

Let G be a graph such that each vertex has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. For two given list colorings of G, we study the problem of transforming one into the other by changing only one vertex color assignment at a time, while at all times maintaining a list coloring. This problem is known to be PSPACE-complete even for bounded bandwidth graphs and a fixed constant k. In this paper, we study the fixed-parameter tractability of the problem when parameterized by several graph parameters. We first give a fixed-parameter algorithm for the problem when parameterized by k and the modular-width of an input graph. We next give a fixed-parameter algorithm for the shortest variant which computes the length of a shortest transformation when parameterized by k and the size of a minimum vertex cover of an input graph. As corollaries of these two results, we show that the problem for cographs and the shortest variant for split graphs are fixed-parameter tractable even when only k is taken as a parameter. On the other hand, we prove that the problem is W [ 1 ] -hard when parameterized only by the size of a minimum vertex cover of an input graph.

TCS Journal 2017 Journal Article

Efficient stabilization of cooperative matching games

• Takehiro Ito
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yoshio Okamoto

Cooperative matching games have drawn much interest partly because of the connection with bargaining solutions in the networking environment. However, it is not always guaranteed that a network under investigation gives rise to a stable bargaining outcome. To address this issue, we consider a modification process, called stabilization, that yields a network with stable outcomes, where the modification should be as small as possible. Therefore, the problem is cast to a combinatorial-optimization problem in a graph. Recently, the stabilization by edge removal was shown to be NP-hard. On the contrary, in this paper, we show that other possible ways of stabilization, namely, edge addition, vertex removal and vertex addition, are all polynomial-time solvable. Thus, we obtain a complete complexity-theoretic classification of the natural four variants of the network stabilization problem. We further study weighted variants and prove that the variants for edge addition and vertex removal are NP-hard.

MFCS Conference 2017 Conference Paper

Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters

• Tatsuhiko Hatanaka
• Takehiro Ito
• Xiao Zhou 0001

Let G be a graph such that each vertex has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. For two given list colorings of G, we study the problem of transforming one into the other by changing only one vertex color assignment at a time, while at all times maintaining a list coloring. This problem is known to be PSPACE-complete even for bounded bandwidth graphs and a fixed constant k. In this paper, we study the fixed-parameter tractability of the problem when parameterized by several graph parameters. We first give a fixed-parameter algorithm for the problem when parameterized by k and the modular-width of an input graph. We next give a fixed-parameter algorithm for the shortest variant which computes the length of a shortest transformation when parameterized by k and the size of a minimum vertex cover of an input graph. As corollaries, we show that the problem for cographs and the shortest variant for split graphs are fixed-parameter tractable even when only k is taken as a parameter. On the other hand, we prove that the problem is W[1]-hard when parameterized only by the size of a minimum vertex cover of an input graph.

AAMAS Conference 2016 Conference Paper

Efficient Stabilization of Cooperative Matching Games

• Takehiro Ito
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yoshio Okamoto

TCS Journal 2016 Journal Article

The complexity of dominating set reconfiguration

• Arash Haddadan
• Takehiro Ito
• Amer E. Mouawad
• Naomi Nishimura
• Hirotaka Ono
• Akira Suzuki
• Youcef Tebbal

Suppose that we are given two dominating sets D s and D t of a graph G whose cardinalities are at most a given threshold k. Then, we are asked whether there exists a sequence of dominating sets of G between D s and D t such that each dominating set in the sequence is of cardinality at most k and can be obtained from the previous one by either adding or deleting exactly one vertex. This decision problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, forests, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence if it exists such that the number of additions and deletions is bounded by O ( n ), where n is the number of vertices in the input graph.

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

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

Complexity of finding maximum regular induced subgraphs with prescribed degree

• Yuichi Asahiro
• Hiroshi Eto
• Takehiro Ito
• Eiji Miyano

We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G [ S ] induced by S is r-regular for a prescribed degree r ≥ 0. We also consider a variant of the problem which requires G [ S ] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs.

TCS Journal 2014 Journal Article

Generalized rainbow connectivity of graphs

• Kei Uchizawa
• Takanori Aoki
• Takehiro Ito
• Xiao Zhou

Let C = { c 1, c 2, …, c k } be a set of k colors, and let ℓ → = ( ℓ 1, ℓ 2, …, ℓ k ) be a k-tuple of nonnegative integers ℓ 1, ℓ 2, …, ℓ k. For a graph G = ( V, E ), let f: E → C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is ℓ → -rainbow connected if every two vertices of G have a path P connecting them such that the number of edges on P that are colored with c j is at most ℓ j for each index j ∈ { 1, 2, …, k }. Given a k-tuple ℓ → and an edge-colored graph, we study the problem of determining whether the edge-colored graph is ℓ → -rainbow connected. In this paper, we first study the computational complexity of the problem with regard to certain graph classes: the problem is NP-complete even for cacti, while is solvable in polynomial time for trees. We then give an FPT algorithm for general graphs when parameterized by both k and ℓ max = max ⁡ { ℓ j | 1 ⩽ j ⩽ k }.

TCS Journal 2014 Journal Article

Reconfiguration of list L ( 2, 1 ) -labelings in a graph

• Takehiro Ito
• Kazuto Kawamura
• Hirotaka Ono
• Xiao Zhou

For an integer k ≥ 0, suppose that each vertex v of a graph G has a set C ( v ) ⊆ { 0, 1, …, k } of labels, called a list of v. A list L ( 2, 1 ) -labeling of G is an assignment of a label in C ( v ) to each vertex v of G such that every two adjacent vertices receive labels which differ by at least 2 and every two vertices of distance two receive labels which differ by at least 1. In this paper, we study the problem of reconfiguring one list L ( 2, 1 ) -labeling of a graph into another list L ( 2, 1 ) -labeling of the same graph by changing only one label assignment at a time, while at all times maintaining a list L ( 2, 1 ) -labeling. First we show that this decision problem is PSPACE-complete, even for bipartite planar graphs and k ≥ 6. In contrast, we then show that the problem can be solved in linear time for general graphs if k ≤ 4. We finally consider the problem restricted to trees, and give a sufficient condition for which any two list L ( 2, 1 ) -labelings of a tree can be transformed into each other.

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 2011 Journal Article

Parameterizing cut sets in a graph by the number of their components

• Takehiro Ito
• Marcin Kamiński
• Daniël Paulusma
• Dimitrios M. Thilikos

For a connected graph G = ( V, E ), a subset U ⊆ V is a disconnected cut if U disconnects G and the subgraph G [ U ] induced by U is disconnected as well. A cut U is a k -cut if G [ U ] contains exactly k ( ≥ 1 ) components. More specifically, a k -cut U is a ( k, ℓ ) -cut if V ∖ U induces a subgraph with exactly ℓ ( ≥ 2 ) components. The Disconnected Cut problem is to test whether a graph has a disconnected cut and is known to be NP-complete. The problems k -Cut and ( k, ℓ ) -Cut are to test whether a graph has a k -cut or ( k, ℓ ) -cut, respectively. By pinpointing a close relationship to graph contractibility problems we show that ( k, ℓ ) -Cut is in P for k = 1 and any fixed constant ℓ ≥ 2, while it is NP-complete for any fixed pair k, ℓ ≥ 2. We then prove that k -Cut is in P for k = 1 and NP-complete for any fixed k ≥ 2. On the other hand, for every fixed integer g ≥ 0, we present an FPT algorithm that solves ( k, ℓ ) -Cut on graphs of Euler genus at most g when parameterized by k + ℓ. By modifying this algorithm we can also show that k -Cut is in FPT for this graph class when parameterized by k. Finally, we show that Disconnected Cut is solvable in polynomial time for minor-closed classes of graphs excluding some apex graph.