Faculty Profiles - ONO Hirotaka

Papers - ONO Hirotaka

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

An improved spectral lower bound of treewidth Reviewed Open Access

Gima, T; Hanaka, T; Noro, K; Ono, H; Otachi, Y

INFORMATION PROCESSING LETTERS Vol. 188 2025.2

Language：English Publisher：Information Processing Letters

We show that for every n-vertex graph with at least one edge, its treewidth is greater than or equal to nλ2/(Δ+λ2)−1, where Δ and λ2 are the maximum degree and the second smallest Laplacian eigenvalue of the graph, respectively. This lower bound improves the one by Chandran and Subramanian [Inf. Process. Lett., 2003] and the subsequent one by the authors of the present paper [IEICE Trans. Inf. Syst., 2024]. The new lower bound is almost tight in the sense that there is an infinite family of graphs such that the lower bound is only 1 less than the treewidth for each graph in the family. Additionally, using similar techniques, we also present a lower bound of treewidth in terms of the largest and the second smallest Laplacian eigenvalues.

DOI： 10.1016/j.ipl.2024.106536

Web of Science

Scopus

Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints Reviewed Open Access

Kobayashi, Y; Kurita, K; Mann, K; Matsui, Y; Ono, H

ALGORITHMS Vol. 18 ( 2 ) 2025.2

Authorship：Last author Language：English Publisher：Algorithms

In this paper, we consider the minimal vertex cover and minimal dominating sets with capacity and/or connectivity constraint enumeration problems. We develop polynomial-delay enumeration algorithms for these problems on bounded-degree graphs. For the case of minimal connected vertex covers, our algorithms run in polynomial delay, even on the class of d-claw free graphs. This result is extended for bounded-degree graphs and outputs in quasi-polynomial time on general graphs. To complement these algorithmic results, we show that the minimal connected vertex cover, minimal connected dominating set, and minimal capacitated vertex cover enumeration problems in 2-degenerated bipartite graphs are at least as hard as enumerating minimal transversals in hypergraphs.

DOI： 10.3390/a18020112

Open Access

Web of Science

Scopus

Structural parameterizations of vertex integrity Reviewed Open Access

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

Shortest Longest-Path Graph Orientations for Trees Reviewed

Asahiro Y., Jansson J., Melkman A.A., Miyano E., Ono H., Xue Q., Yano Y., Zakov S.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 15538 LNCS page： 51 - 64 2025

Language：English Publisher：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Graph orientation transforms an undirected graph into a directed graph by assigning a direction to each edge. Among the many different optimization problems related to graph orientations, we focus here on the Shortest Longest-Path Orientation problem (SLPO) which is a generalization of the well-known Minimum Graph Coloring problem. The input to SLPO is an edge-bi-weighted undirected graph in which every edge has two (possibly different and not necessarily positive) lengths associated with its two directions. The goal is to find an orientation of the input graph that minimizes the length of the longest simple directed path. Recently, polynomial-time algorithms for simple graph structures such as paths, cycles, stars, and trees were proposed, and a new polynomial-time inapproximability result was also established. This paper presents (i) an O(n2logn)-time algorithm for trees, which is a significant improvement over the previously fastest algorithm whose time complexity was Ω(n14) and (ii) polynomial-time algorithms for trees and spiders that run even faster than (i) as long as every edge weight is an integer and the total weight of the edges is sub-exponential.

DOI： 10.1007/978-3-031-82670-2_5

Scopus

Algorithms for Optimally Shifting Intervals Under Intersection Graph Models Reviewed

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 14752 LNCS page： 66 - 78 2025

Authorship：Last author 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 L1 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

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

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 S1,S2,…,Sk such that the size of each unit Si is r and the subgraph of G induced by Si 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 (MSO2). 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

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

Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

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

An 8-approximation algorithm for L(2,1)-labeling of unit disk graphs

Hirotaka Ono, Hisato Yamanaka

Discrete Applied Mathematics Vol. 341 page： 93 - 101 2023.12

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

Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

IPDPS Workshops 2023 Vol. abs/2303.01290 2023.5

Sequentially Swapping Tokens: Further on Graph Classes.

Hironori Kiya, Yuto Okada, Hirotaka Ono, Yota Otachi

SOFSEM 2023: Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science(SOFSEM) Vol. 13878 page： 222 - 235 2023

Approximation Algorithms for the Longest Run Subsequence Problem. Reviewed

小野廣隆

Leibniz International Proceedings in Informatics (LIPIcs) Vol. 259 2023

Shortest Beer Path Queries Based on Graph Decomposition.

Tesshu Hanaka, Hirotaka Ono 0001, Kunihiko Sadakane, Kosuke Sugiyama

ISAAC Vol. 283 page： 37 - 20 2023

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

Hanaka, T; Ono, H; Sugiyama, K

2023 IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS, IPDPSW page： 308 - 313 2023

Publisher：2023 IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2023

For an undirected graph G=(V, E) and a k-nonnegative integer vector p=(p_1, L˙, p_k), a mapping l: V → N ∪0 is called an L(p)-labeling of G if |l(u)-l(v)| ≥ p_d for any two distinct vertices u, v in V with distance d, and the maximum value of l(v) mid v in 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 O2^n n^2) time, where n is the number of vertices, and so on.

DOI： 10.1109/IPDPSW59300.2023.00059

Web of Science

Scopus

　 PREV - NEXT 　

<ONO Hirotaka>

Papers - ONO Hirotaka