Author name cluster

Masashi Kiyomi

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.

8 papers

1 author row

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

TCS Journal 2020 Journal Article

Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs

Kazuaki Yamazaki
Toshiki Saitoh
Masashi Kiyomi
Ryuhei Uehara

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

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

TCS Journal 2010 Journal Article

Reconstruction of interval graphs

Masashi Kiyomi
Toshiki Saitoh
Ryuhei Uehara

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

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