Arrow Research search

Author name cluster

Kunihiro Wasa

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.

13 papers
2 author rows

Possible papers

13

I&C Journal 2025 Journal Article

Polynomial-delay enumeration of large maximal common independent sets in two matroids and beyond

  • Yasuaki Kobayashi
  • Kazuhiro Kurita
  • Kunihiro Wasa

Finding a maximum cardinality common independent set in two matroids (also known as Matroid Intersection) is a classical combinatorial optimization problem, which generalizes several well-known problems, such as finding a maximum bipartite matching, a maximum colorful forest, and an arborescence in directed graphs. Enumerating all maximal common independent sets in two (or more) matroids is a classical enumeration problem. In this paper, we address an “intersection” of these problems: Given two matroids and a threshold τ, the goal is to enumerate all maximal common independent sets in the matroids with cardinality at least τ. We show that this problem can be solved in polynomial delay and polynomial space. Moreover, our technique can be extended to a more general problem, which is relevant to Matroid Matching. We give a polynomial-delay and polynomial-space algorithm for enumerating all maximal “matchings” with cardinality at least τ, assuming that the optimization counterpart is “tractable” in a certain sense. This extension allows us to enumerate small minimal connected vertex covers in subcubic graphs. We also discuss a framework to convert enumeration with cardinality constraints into ranked enumeration.

Details DOI

TCS Journal 2025 Journal Article

Reconfiguration and enumeration of optimal cyclic ladder lotteries

  • Yuta Nozaki
  • Kunihiro Wasa
  • Katsuhisa Yamanaka

A ladder lottery, known as “Amidakuji” in Japan, is a common way to decide an assignment at random. In this paper, we investigate reconfiguration and enumeration problems of cyclic ladder lotteries. First, when a permutation π and an optimal displacement vector x are given, we investigate the reconfiguration and enumeration problems of the “optimal” cyclic ladder lotteries of π and x. Next, for a given permutation π we consider reconfiguration and enumeration problems of the optimal displacement vectors of π.

Details DOI

TCS Journal 2024 Journal Article

An approximation algorithm for K-best enumeration of minimal connected edge dominating sets with cardinality constraints

  • Kazuhiro Kurita
  • Kunihiro Wasa

K-best enumeration, which asks to output k-best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, k-best enumeration tends to be intractable since, in many cases, finding one optimum solution is NP-hard. To overcome this difficulty, we combine k-best enumeration with a concept of enumeration algorithms called approximation enumeration algorithms. As a main result, we propose a 4-approximation algorithm for minimal connected edge dominating sets which outputs k minimal solutions with cardinality at most 4 ⋅ OPT ‾, where OPT ‾ is the cardinality of a minimum solution which is not outputted by the algorithm. Our proposed algorithm runs in O ( n m 2 Δ ) delay, where n, m, Δ are the number of vertices, the number of edges, and the maximum degree of an input graph.

Details DOI

MFCS Conference 2023 Conference Paper

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids

  • Yasuaki Kobayashi
  • Kazuhiro Kurita
  • Kunihiro Wasa

Finding a maximum cardinality common independent set in two matroids (also known as Matroid Intersection) is a classical combinatorial optimization problem, which generalizes several well-known problems, such as finding a maximum bipartite matching, a maximum colorful forest, and an arborescence in directed graphs. Enumerating all maximal common independent sets in two (or more) matroids is a classical enumeration problem. In this paper, we address an "intersection" of these problems: Given two matroids and a threshold τ, the goal is to enumerate all maximal common independent sets in the matroids with cardinality at least τ. We show that this problem can be solved in polynomial delay and polynomial space. We also discuss how to enumerate all maximal common independent sets of two matroids in non-increasing order of their cardinalities.

Details

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

Constant amortized time enumeration of Eulerian trails

  • Kazuhiro Kurita
  • Kunihiro Wasa

In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Two Eulerian trails are said to be edge-distinct if the edge sequences are not identical, and they are said to be vertex-distinct if the vertex sequences are not identical. To solve these problems, we propose optimal enumeration algorithms that run in O ( N + m ) total time, where N is the number of solutions and m is the number of edges in an input connected graph. The proposed algorithms are based on the reverse search technique introduced by [Avis and Fukuda, DAM 1996], and the push-out amortization technique introduced by [Uno, WADS 2015].

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

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

Optimal reconfiguration of optimal ladder lotteries

  • Katsuhisa Yamanaka
  • Takashi Horiyama
  • Kunihiro Wasa

A ladder lottery, known as “Amidakuji” in Japan, is a common way to decide an assignment at random. A ladder lottery L of a given permutation is optimal if L has the minimum number of horizontal lines. In this paper, we investigate a reconfiguration problem of optimal ladder lotteries. The reconfiguration problem on a set of optimal ladder lotteries asks, given two optimal ladder lotteries L, L ′ of a permutation π, to find a sequence of 〈 L 1, L 2, …, L k 〉 of optimal ladder lotteries of π such that (1) L 1 = L and L k = L ′ and (2) L i for i = 2, 3, …, k is obtained from L i − 1 by moving a bar in L i − 1 locally. An existing result implies that any two optimal ladder lotteries of a permutation π have a reconfiguration sequence of length O ( n 3 ), where n is the number of elements in π. In this paper, we characterize the minimum length of reconfiguration sequences between two optimal ladder lotteries. Moreover, we present a linear-time algorithm that computes the minimum length.

Details DOI

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.

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

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.

Details
v2026.09.13