Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

Division display 1 - 20 of about 260 ／ All the affair displays >>

Faster winner determination algorithms for (Colored) Arc Kayles

Hanaka, T; Kiya, H; Lampis, M; Ono, H; Yoshiwatari, K

JOURNAL OF COMPUTER AND SYSTEM SCIENCES Vol. 156 2026.3

Publisher：Journal of Computer and System Sciences

ARC KAYLES and COLORED ARC KAYLES are generalized versions of well-studied combinatorial games CRAM and DOMINEERING, respectively. In ARC KAYLES, two players alternately choose an edge to remove with its adjacent edges, and the player who cannot move is the loser. COLORED ARC KAYLES is similarly played on a graph with edges colored in black, white, or gray, in which the black (resp., white) player can choose only a gray or black (resp., white) edge. For ARC KAYLES, the vertex cover number τ (i.e., the minimum size of a vertex cover) is an essential invariant because it is known that twice the vertex cover number upper bounds the number of turns of ARC KAYLES, and for the winner determination of (COLORED) ARC KAYLES, 2O(τ2)nO(1)-time algorithms are known, where n is the number of vertices. In this paper, we first give a polynomial kernel for COLORED ARC KAYLES parameterized by τ, which leads to a faster 2O(τlog⁡τ)nO(1)-time algorithm for COLORED ARC KAYLES. We then focus on ARC KAYLES on trees, and propose a 2.2361τnO(1)-time algorithm. Furthermore, we show that determining the winner of ARC KAYLES on a tree can be done in O(1.3831n) time, which improves the best-known running time of O(1.4143n). Finally, we show that COLORED ARC KAYLES is NP-hard, the first hardness result in the family of the above games.

DOI： 10.1016/j.jcss.2025.103716

Web of Science

Scopus

Approximability of Longest Run Subsequence and Complementary Minimization Problems Open Access

Asahiro Y., Jansson J., Lu S., Ono H., Tanaka S., Gong M., Lin G., Miyano E., Saitoh T.

Leibniz International Proceedings in Informatics Lipics Vol. 344 2025.8

Publisher：Leibniz International Proceedings in Informatics Lipics

We study the polynomial-time approximability of the Longest Run Subsequence problem (LRS for short) and its complementary minimization variant Minimum Run Subsequence Deletion problem (MRSD for short). For a string S = s1 · · · sn over an alphabet Σ, a subsequence S′ of S is S′ = si<inf>1</inf> · · · si<inf>p</inf>, such that 1 ≤ i1 < i2 < . . . < ip ≤ |S|. A run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S′ of S is a subsequence of S in which every symbol σ ∈ Σ occurs in at most one run. The co-subsequence S′ of the subsequence S′ = si<inf>1</inf> · · · si<inf>p</inf> in S is the subsequence obtained by deleting all the characters in S′ from S, i.e., S′ = sj<inf>1</inf> · · · sj<inf>n</inf>−<inf>p</inf> such that j1 < j2 < . . . < jn−p and {j1, . . ., jn−p} = {1, . . ., n} \ {i1, . . ., ip}. Given a string S, the goal of LRS (resp., MRSD) is to find a run subsequence S∗ of S such that the length |S∗| is maximized (resp., the number |S∗| of deleted symbols from S is minimized) over all the run subsequences of S. Let k be the maximum number of symbol occurrences in the input S. It is known that LRS and MRSD are APX-hard even if k = 2. In this paper, we show that LRS can be approximated in polynomial time within factors of (k + 2)/3 for k = 2 or 3, and 2(k + 1)/5 for every k ≥ 4. Furthermore, we show that MRSD can be approximated in linear time within a factor of (k + 4)/4 if k is even and (k + 3)/4 if k is odd.

DOI： 10.4230/LIPIcs.WABI.2025.3

Open Access

Scopus

Enumeration of Ordered Trees with Leaf Restrictions Open Access

Kobayashi Y., Köppl D., Matsui Y., Ono H., Saitoh T., Uno Y.

Openaccess Series in Informatics Vol. 132 2025.8

Publisher：Openaccess Series in Informatics

An α-ary tree for a constant α ≥ 2 is a rooted tree in which each node has at most α children. A node having no children is called a leaf. For a given rooted tree and a node v, the number of edges from the root to v is called the depth of v. We call a vector w = (w1, w2, . . ., w<inf>d</inf>) of nonnegative integers an (α-ary) distribution if there is an α-ary tree T such that the number of leaves at each depth i ∈ [1..d] in T is wi. Although not every vector of nonnegative integers is a distribution, a distribution can be associated with many α-ary trees. In this paper, we present an algorithm to enumerate all α-ary trees for a given distribution. Our algorithm reports the first tree in O(d + ∑d<inf>i</inf><inf>=1</inf> wi) time, and then each subsequent α-ary tree in O(maxd<inf>i</inf><inf>=1</inf> wi) time by representing each tree as the difference from the previous one. The algorithm can be restricted to computing all trees that are full, i.e., trees whose nodes have exactly α or no children.

DOI： 10.4230/OASIcs.Grossi.2025.8

Open Access

Scopus

Structural parameterizations of vertex integrity Reviewed

Gima, T; Hanaka, T; Kobayashi, Y; Murai, R; Ono, H; Otachi, Y

THEORETICAL COMPUTER SCIENCE Vol. 1024 2025.1

Language：English Publisher：Theoretical Computer Science

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.

DOI： 10.1016/j.tcs.2024.114954

Web of Science

Scopus

Algorithms for Optimally Shifting Intervals Under Intersection Graph Models Reviewed

Honorato-Droguett, N; Kurita, K; Hanaka, T; Ono, H

FRONTIERS OF ALGORITHMICS, IJTCS-FAW 2024 Vol. 14752 page： 66 - 78 2025

Language：English Publisher：Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics

We propose a new model for graph editing problems on intersection graphs. In well-studied graph editing problems, adding and deleting vertices and edges are used as graph editing operations. As a graph editing operation on intersection graphs, we propose moving objects corresponding to vertices. In this paper, we focus on interval graphs as an intersection graph. We give a linear-time algorithm to find the total moving distance for transforming an interval graph into a complete graph. The concept of this algorithm can be applied for (i) transforming a unit square graph into a complete graph over L<inf>1</inf> distance and (ii) attaining the existence of a k-clique on unit interval graphs. In addition, we provide LP-formulations to achieve several properties in the associated graph of unit intervals.

DOI： 10.1007/978-981-97-7752-5_5

Web of Science

Scopus

Hardness Results on Generalized Puyo Puyo Open Access

Eto Hiroshi, Kiya Hironori, Ono Hirotaka

Journal of Information Processing Vol. 33 ( 0 ) page： 1077 - 1091 2025

Language：English Publisher：Information Processing Society of Japan

Puyo Puyo is a Tetris-like falling-block video game, which has been played in Japan more than 30 years. In Tetris, tetrominoes fall on the board, whereas colored and colorless “puyo”s fall in Puyo Puyo. The clearing rule in Tetris is to fill a line (row) of the board, whereas that in Puyo Puyo is to make a cluster with a size of at least 4 puyos with a single color. A colorless puyo is cleared only when a colored puyo touching it is cleared. Due to this clearing rule, a clearing chain phenomenon arises, which is a unique nature of Puyo Puyo. In this paper, we investigate the computational complexity of a generalized Puyo Puyo, where the size of the board and the number of colors are arbitrary, but the falling sequence of puyos is given in an offline manner. We focus on two algorithmic problems in the generalized Puyo Puyo. One is the problem of finding a clearing chain with the longest length for a given board and a falling sequence of puyos, and the other is the problem of deciding whether a given board and a falling sequence of puyos can clear all the puyos, or not. Both problems are already known to be NP-complete. The former problem, the longest clearing chain problem, is shown to be NP-complete even if the number of colors is 4. The latter problem, the all-clear problem, is also shown to be NP-complete even if the number of colors is 2. In this paper, we strengthen these results: (1) The longest clearing chain problem is NP-complete even if the number of colors is 2. (2) The longest clearing chain cannot be approximated within a factor better than any polynomial of the falling sequence length in polynomial time unless P = NP.

DOI： 10.2197/ipsjjip.33.1077

Open Access

Scopus

CiNii Research

Structural Parameters for Steiner Orientation

Hanaka T., Lampis M., Melissinos N., Nemery E., Ono H., Vasilakis M.

Leibniz International Proceedings in Informatics Lipics Vol. 359 2025

Publisher：Leibniz International Proceedings in Informatics Lipics

We consider the Steiner Orientation problem, where we are given as input a mixed graph G = (V, E, A) and a set of k demand pairs (si, ti), i ∈ [k]. The goal is to orient the undirected edges of G in a way that the resulting directed graph has a directed path from si to ti for all i ∈ [k]. We adopt the point of view of structural parameterized complexity and investigate the complexity of Steiner Orientation for standard measures, such as treewidth. Our results indicate that Steiner Orientation is a surprisingly hard problem from this point of view. In particular, our main contributions are the following: 1. We show that Steiner Orientation is NP-complete on instances where the underlying graph has feedback vertex number 2, treewidth 2, pathwidth 3, and vertex integrity 6. 2. We present an XP algorithm parameterized by vertex cover number vc of complexity nO(vc2). Furthermore, we show that this running time is essentially optimal by proving that a running time of no(vc2) would refute the ETH. 3. We consider parameterizations by the number of undirected or directed edges (|E| or |A|) and we observe that the trivial 2|E|nO(1)-time algorithm for the former parameter is optimal under the SETH. Complementing this, we show that the problem admits a 2O(|A|)nO(1)-time algorithm. In addition to the above, we consider the complexity of Steiner Orientation parameterized by tw + k (FPT), distance to clique (FPT), and vc + k (FPT with a polynomial kernel).

DOI： 10.4230/LIPIcs.ISAAC.2025.38

Scopus

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Koki Suetsugu, Kanae Yoshiwatari: Computational complexity of Turning Tiles Reviewed

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Koki Suetsugu, Kanae Yoshiwatari

International Journal of Game Theory Vol. 53 ( 4 ) 2024.10

Polynomial-time equivalences and refined algorithms for longest common subsequence variants Reviewed Open Access

Asahiro, Y; Jansson, J; Lin, GH; Miyano, E; Ono, H; Utashima, T

DISCRETE APPLIED MATHEMATICS Vol. 353 page： 44 - 64 2024.8

Language：English Publisher：Discrete Applied Mathematics

The problem of computing the longest common subsequence of two sequences (LCS for short) is a classical and fundamental problem in computer science. In this article, we study four variants of LCS: the REPETITION-BOUNDED LONGEST COMMON SUBSEQUENCE problem (RBLCS), the MULTISET-RESTRICTED COMMON SUBSEQUENCE problem (MRCS), the TWO-SIDE-FILLED LONGEST COMMON SUBSEQUENCE problem (2FLCS), and the ONE-SIDE-FILLED LONGEST COMMON SUBSEQUENCE problem (1FLCS). Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O(1.44225n)-time, dynamic programming (DP) based algorithm for RBLCS was proposed, where the two input sequences have lengths n and poly(n). Here, we first establish that each of MRCS, 1FLCS, and 2FLCS is polynomially equivalent to RBLCS. Then, we design a refined DP-based algorithm for RBLCS that runs in O(1.41422n) time, which implies that MRCS, 1FLCS, and 2FLCS can also be solved in O(1.41422n) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS.

DOI： 10.1016/j.dam.2024.04.006

Web of Science

Scopus

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

Hanaka, T; Ono, H; Otachi, Y; Uda, S

THEORETICAL COMPUTER SCIENCE Vol. 996 2024.5

Language：English Publisher：Theoretical Computer Science

A dominating set S of graph G is called an r-grouped dominating set if S can be partitioned into S<inf>1</inf>,S<inf>2</inf>,…,S<inf>k</inf> such that the size of each unit S<inf>i</inf> is r and the subgraph of G induced by S<inf>i</inf> 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<inf>2</inf>). 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.

DOI： 10.1016/j.tcs.2024.114507

Web of Science

Scopus

Winner Determination Algorithms for Graph Games with Matching Structures.

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Kanae Yoshiwatari

Algorithmica Vol. 86 ( 3 ) page： 808 - 824 2024.3

Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover. Open Access

Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono 0001, Kazuhisa Seto, Ryu Suzuki

AAAI Vol. 38 ( 18 ) page： 20726 - 20734 2024

Faster Winner Determination Algorithms for (Colored) Arc Kayles

Tesshu Hanaka, Hironori Kiya, Michael Lampis, Hirotaka Ono, Kanae Yoshiwatari

Vol. 14519 page： 297 - 310 2024

Structural Parameterizations of Vertex Integrity

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

Vol. 14549 page： 406 - 420 2024

Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP

Hanaka Tesshu, Ono Hirotaka, Sugiyama Kosuke

International Journal of Networking and Computing Vol. 14 ( 1 ) page： 26 - 39 2024

Language：English Publisher：IJNC Editorial Committee

For an undirected graph G = (V,E) and a k-non-negative integer vector p = (p1, . . . , pk), a mapping l : V → N∪{0} is called an L(p)-labeling of G if |l(u) − l(v)| ≥ pd for any two distinct vertices u, v ∈ V with distance d, and the maximum value of {l(v) | v ∈ V } is called the span of l. Originally, L(p)-labeling of G for p = (2, 1) is introduced in the context of frequency assignment in radio networks, where ‘close’ transmitters must receive different frequencies and ‘very close’ transmitters must receive frequencies that are at least two frequencies apart so that they can avoid interference. L(p)-Labeling is the problem of finding the minimum span λp among L(p)-labelings of G, which is NP-hard for every non-zero p. L(p)-Labeling is well studied for specific p’s; in particular, many (exact or approximation) algorithms for general graphs or restricted classes of graphs are proposed for p = (2, 1) or more generally p = (p, q). Unfortunately, most algorithms strongly depend on the values of p, and it is not apparent to extend algorithms for p to ones for another p′ in general. In this paper, we give a simple polynomial-time reduction of L(p)-Labeling on graphs with a small diameter to Metric (Path) TSP, which enables us to use numerous results on (Metric) TSP. On the practical side, we can utilize various high-performance heuristics for TSP, such as Concordo and LKH, to solve our problem. On the theoretical side, we can see that the problem for any p under this framework is 1.5-approximable, and it can be solved by the Held-Karp algorithm in O(2nn2) time, where n is the number of vertices, and so on.

DOI： 10.15803/ijnc.14.1_26

CiNii Research

Maximizing utilitarian and Egalitarian welfare of fractional hedonic games on tree-like graphs

Tesshu Hanaka, Airi Ikeyama, Hirotaka Ono

Journal of Combinatorial Optimization Vol. 14461 LNCS ( 3 ) page： 392 - 405 2024