研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 260 件中 41 - 60 件目／全件表示 >>

Hedonic Seat Arrangement Problems 査読有り国際共著

小野廣隆

Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '20, Auckland, New Zealand - 巻頁： 1777 - 1779 2020年

Sequentially swapping tokens: Further on graph classes ☆,☆☆

Kiya, H; Okada, Y; Ono, H; Otachi, Y

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 155 巻頁： 103691 - 103691 2026年2月

掲載種別：研究論文（学術雑誌）出版者・発行元：Journal of Computer and System Sciences

In this paper, we study SEQUENTIAL TOKEN SWAPPING, which can be seen as a variant of the generalized 15 puzzle. Given a graph and two token placements on the vertices, the problem asks to find a walk of the minimum length (if any exists) such that the sequence of token swappings along the walk obtains one of the given token placements from the other one. This problem was introduced by Yamanaka et al. [JGAA 2019], who showed that the problem is intractable in general but polynomial-time solvable for trees, complete graphs, and cycles. In this paper, we present a polynomial-time algorithm for block-cactus graphs, which include all previously known cases. We also present general tools for showing the hardness of the problem on restricted graph classes such as chordal graphs and chordal bipartite graphs. We also show that the problem is hard on grids and king's graphs, which are the graphs corresponding to the 15 puzzle and its variant with relaxed moves.

DOI： 10.1016/j.jcss.2025.103691

Finding a HIST: Chordality, Structural Parameters, and Diameter

Hanaka T., Kiya H., Ono H.

Lecture Notes in Computer Science 16448 LNCS 巻頁： 303 - 316 2026年

出版者・発行元：Lecture Notes in Computer Science

A homeomorphically irreducible spanning tree (HIST) is a spanning tree with no degree-2 vertices, serving as a structurally minimal backbone of a graph. While the existence of HISTs has been widely studied from a structural perspective, the algorithmic complexity of finding them remains less understood. In this paper, we provide a comprehensive investigation of the HIST problem from both structural and algorithmic viewpoints. We present a simple characterization that precisely describes which chordal graphs of diameter at most 3 admit a HIST, leading to a polynomial-time decision procedure for this class. In contrast, we show that the problem is NP-complete for strongly chordal graphs of diameter 4. From the perspective of parameterized complexity, we establish that the HIST problem is W[1]-hard when parameterized by clique-width, indicating that the problem is unlikely to be efficiently solvable in general dense graphs. On the other hand, we present fixed-parameter tractable (FPT) algorithms when parameterized by treewidth, modular-width, or cluster vertex deletion number. Specifically, we develop an O<sup>∗</sup>(4<sup>k</sup>)-time algorithm parameterized by modular-width k, and an FPT algorithm parameterized by the cluster vertex deletion number based on kernelization techniques that bound clique sizes while preserving the existence of a HIST. These results together provide a clearer understanding of the structural and computational boundaries of the HIST problem.

DOI： 10.1007/978-3-032-17801-5_23

Colored Node Kayles: Algorithms and Computational Complexity

Hanaka T., Ono H., Yoshiwatari K.

Lecture Notes in Computer Science 16366 LNAI 巻頁： 461 - 478 2026年

出版者・発行元：Lecture Notes in Computer Science

Colored Node Kayles is a combinatorial game played on an undirected graph G=(V,E) with vertex colors from black, gray, white. Two players, Black and White, alternate turns: Black selects a gray or black vertex, while White selects a gray or white vertex. The chosen vertex and its neighbors are then removed from G. The game continues until no valid moves remain, with the last player able to move declared the winner. Node Kayles, the special case of Colored Node Kayles with only gray vertices, has been extensively studied. Due to its simplicity and generality, results for Node Kayles have been applied to a broad range of other combinatorial games, though the partisan variant Colored Node Kayles has received far less attention. A restricted version, called Bigraph Node Kayles, was implicitly introduced by Schaefer in his seminal 1978 work, where one side of a bipartite graph is colored black and the other white. We formally define Colored Node Kayles and study the complexity of deciding the winner. We prove that it is PSPACE-complete even on planar graphs with maximum degree 3. We also show W[1]-hardness with respect to the number of turns and present other hardness results, including for computing game values. On the algorithmic side, Colored Node Kayles is FPT concerning graph structural parameters such as clique deletion number, neighborhood diversity, vertex cover, and twin cover, and is solvable in polynomial time on graphs with bounded vertex integrity or cluster deletion number.

DOI： 10.1007/978-3-032-13562-9_36

Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion

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

Lecture Notes in Computer Science 16444 LNCS 巻頁： 451 - 466 2026年

出版者・発行元：Lecture Notes in Computer Science

Removing overlaps is a central task in domains such as scheduling, visibility, and map labelling. This can be modelled using graphs, where overlap removals correspond to enforcing a certain sparsity constraint on the graph structure. We continue the study of the problem Geometric Graph Edit Distance (GGED), where the aim is to minimise the total cost of editing a geometric intersection graph to obtain a graph contained in a specific graph class. For us, the edit operation is the movement of objects, and the cost is the movement distance. We present an algorithm for rendering the intersection graph of a set of unit circular arcs (i) edgeless, (ii) acyclic, and (iii) k-clique-free in O(nlogn) time, where n is the number of arcs. We also show that GGED remains strongly NP-hard on unweighted interval graphs, solving an open problem of Honorato-Droguett et al. [WADS 2025]. We complement this result by showing that GGED is strongly NP-hard on sets of d-balls and d-cubes, for any d≥2. Finally, we present an XP algorithm (parameterised by the number of maximal cliques) that removes all edges from the intersection graph of a set of weighted unit intervals.

DOI： 10.1007/978-981-95-7127-7_30

Reallocation Problems with Minimum Completion Time

Ishii, T; Kawahara, J; Makino, K; Ono, H

ALGORITHMICA 87 巻 ( 9 ) 頁： 1311 - 1339 2025年9月

掲載種別：研究論文（学術雑誌）出版者・発行元：Algorithmica

Reallocation scheduling is one of the most fundamental problems in various areas such as supply chain management, logistics, and transportation science. In this paper, we introduce the reallocation problem that models the scheduling in which products are with fixed cost (e.g., transition time), non-fungible, and reallocated among warehouses in parallel, and comprehensively study the complexity of the problem under various settings of the transition time, product size, and capacities. We show that the problem can be solved in polynomial time for a fundamental setting where the product size and transition time are both uniform. We also show that the feasibility of the problem is NP-complete even for little more general settings, which implies that no polynomial-time algorithm constructs a feasible schedule of the problem unless P=NP. We then consider to solve the problem by relaxing capacity constraints, which we call the capacity augmentation, and derive a reallocation schedule feasible with the augmentation such that the completion time is at most the optimal of the original problem. When the warehouse capacity is sufficiently large, we design constant-factor approximation algorithms. We also show the relationship between the reallocation problem and the bin packing problem when the warehouse and carry-in capacities are sufficiently large.

DOI： 10.1007/s00453-025-01320-0

その他リンク： https://link.springer.com/article/10.1007/s00453-025-01320-0/fulltext.html

Hedonic seat arrangement problems Open Access

Bodlaender, HL; Hanaka, T; Jaffke, L; Ono, H; Otachi, Y; van der Zanden, TC

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 39 巻 ( 2 ) 頁： 33 - 33 2025年7月

掲載種別：研究論文（学術雑誌）出版者・発行元：Autonomous Agents and Multi Agent Systems

In this paper, we study a variant of hedonic games, called Seat Arrangement. The model is defined by a bijection from agents with preferences for each other to vertices in a graph G. The utility of an agent depends on the neighbors assigned in the graph. More precisely, it is the sum over all neighbors of the preferences that the agent has towards the agent assigned to the neighbor. We first consider the price of stability and fairness for different classes of preferences. In particular, we show that there is an instance such that the price of fairness (PoF) is unbounded in general. Moreover, we show an upper bound and an almost tight lower bound of PoF, where is the average degree of an input graph. Then we investigate the computational complexity of problems to find certain “good” seat arrangements, say Utilitarian Arrangement, Egalitarian Arrangement, Stable Arrangement, and Envy-free Arrangement. We give dichotomies of computational complexity of four Seat Arrangement problems from the perspective of the maximum order of connected components in an input graph. For the parameterized complexity, Utilitarian Arrangement can be solved in time, while it cannot be solved in time under ETH, where n is the number of agents and is the vertex cover number of an input graph. Moreover, we show that Egalitarian Arrangement and Envy-free Arrangement are weakly NP-hard even on graphs of bounded vertex cover number. Finally, we prove that determining whether a stable arrangement can be obtained from a given arrangement by k swaps is W[1]-hard when parameterized by, whereas it can be solved in time.

DOI： 10.1007/s10458-025-09711-x

Fair Ride Allocation on a Line Open Access

Amano, Y; Igarashi, A; Kawase, Y; Makino, K; Ono, H

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 13 巻 ( 1 ) 2025年3月

掲載種別：研究論文（学術雑誌）出版者・発行元：ACM Transactions on Economics and Computation

The airport problem is a classical and well-known model of fair cost-sharing for a single facility among multiple agents. This article extends it to a more general setting involving multiple facilities. Specifically, in our model, each agent selects a facility and shares the cost with the other agents using the same facility. This scenario frequently occurs in sharing economies, such as sharing subscription costs for a multi-user license or taxi fares among customers traveling to potentially different destinations along a route. Our model can be viewed as a coalition formation game with size constraints, based on the fair cost-sharing of the airport problem. We refer to our model as a fair ride allocation on a line. We incorporate Nash stability and envy-freeness as criteria for solution concepts in our setting. We show that if a feasible allocation exists, a Nash stable feasible allocation that minimizes the social cost of agents exists and can be computed efficiently. Regarding envy-freeness, we provide several structural properties of envy-free allocations. Based on these properties, we design efficient algorithms for finding an envy-free allocation when either (1) the number of facilities, (2) the number of agent types, or (3) the capacity of facilities, is small. Moreover, we show that a consecutive envy-free allocation can be computed in polynomial time. On the negative front, we show NP-completeness of determining the existence of an allocation under two relaxed envy-free concepts.

DOI： 10.1145/3708491

Fair Ride Allocation on a Line 査読有り

Yuki Amano, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hirotaka Ono

ACM Transactions on Economics and Computation 2025年2月

Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints 査読有り Open Access

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

ALGORITHMS 18 巻 ( 2 ) 頁： 112 - 112 2025年2月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：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

An improved spectral lower bound of treewidth 査読有り

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

INFORMATION PROCESSING LETTERS 188 巻頁： 106536 - 106536 2025年2月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：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λ<inf>2</inf>/(Δ+λ<inf>2</inf>)−1, where Δ and λ<inf>2</inf> 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

On the Complexity of Minimising the Moving Distance for Dispersing Objects.

Nicolás Honorato Droguett, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono 0001

CoRR abs/2502.12903 巻 2025年2月

Shortest Longest-Path Graph Orientations for Trees 査読有り

Asahiro, Y; Jansson, J; Melkman, AA; Miyano, E; Ono, H; Xue, Q; Yano, Y; Zakov, S

SOFSEM 2025: THEORY AND PRACTICE OF COMPUTER SCIENCE, SOFSEM 2025, PT I 15538 巻頁： 51 - 64 2025年

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：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(n<sup>2</sup>logn)-time algorithm for trees, which is a significant improvement over the previously fastest algorithm whose time complexity was Ω(n<sup>14</sup>) 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

その他リンク： https://dblp.uni-trier.de/db/conf/sofsem/sofsem2025-1.html#AsahiroJMMOXYZ25

On the Complexity of Minimising the Moving Distance for Dispersing Objects Open Access

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

Leibniz International Proceedings in Informatics Lipics 349 巻頁： 36 - 14 2025年

掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Leibniz International Proceedings in Informatics Lipics

We study Geometric Graph Edit Distance (GGED), a graph-editing model to compute the minimum edit distance of intersection graphs that uses moving objects as an edit operation. We first show an O(n log n)-time algorithm that minimises the total moving distance to disperse unit intervals. This algorithm is applied to render a given unit interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. We next show that GGED becomes strongly NP-hard when rendering a weighted interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. Lastly, we prove that minimising the maximum moving distance for rendering a unit disk graph edgeless is strongly NP-hard over the L1 and L2 distances.

DOI： 10.4230/LIPIcs.WADS.2025.36

その他リンク： https://dblp.uni-trier.de/db/conf/wads/wads2025.html#DroguettKH025

Enumeration of Ordered Trees with Leaf Restrictions. Open Access

Yasuaki Kobayashi, Dominik Köppl, Yasuko Matsui, Hirotaka Ono 0001, Toshiki Saitoh, Yushi Uno

From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday 頁： 8 - 19 2025年

Computational complexity of <sc>Turning Tiles</sc>

Hanaka, T; Kiya, H; Ono, H; Suetsugu, K; Yoshiwatari, K

INTERNATIONAL JOURNAL OF GAME THEORY 53 巻 ( 4 ) 頁： 1211 - 1222 2024年12月

掲載種別：研究論文（学術雑誌）出版者・発行元：International Journal of Game Theory

In combinatorial game theory, the winning player for a position in normal play is analyzed and characterized via algebraic operations. Such analyses define a value for each position, called a game value. A game (ruleset) is called universal if any game value is achievable in some position in a play of the game. Although the universality of a game implies that the ruleset is rich enough (i.e., sufficiently complex), it does not immediately imply that the game is intractable in the sense of computational complexity. This paper proves that the universal game Turning Tiles is PSPACE-complete. We also give other positive and negative results on the computational complexity of Turning Tiles.

DOI： 10.1007/s00182-024-00908-0

その他リンク： https://link.springer.com/article/10.1007/s00182-024-00908-0/fulltext.html

Safe sets and in-dominating sets in digraphs

Bai, YD; Bang-Jensen, J; Fujita, S; Ono, H; Yeo, AD

DISCRETE APPLIED MATHEMATICS 346 巻頁： 215 - 227 2024年3月

掲載種別：研究論文（学術雑誌）出版者・発行元：Discrete Applied Mathematics

A non-empty subset S of the vertices of a digraph D is a safe set if (i) for every strongly connected component M of D−S, there exists a strongly connected component N of D[S] such that there exists an arc from M to N; and (ii) for every strongly connected component M of D−S and every strongly connected component N of D[S], we have |M|≤|N| whenever there exists an arc from M to N. In the case of acyclic digraphs a set X of vertices is a safe set precisely when X is an in-dominating set, that is, every vertex not in X has at least one arc to X. We prove that, even for acyclic digraphs which are traceable (have a hamiltonian path) it is NP-hard to find a minimum cardinality safe (in-dominating) set. Then we show that the problem is also NP-hard for tournaments and give, for every positive constant c, a polynomial algorithm for finding a minimum cardinality safe set in a tournament on n vertices in which no strong component has size more than clog(n). Under the so called Exponential Time Hypothesis (ETH) this is close to best possible in the following sense: If ETH holds, then, for every ϵ>0 there is no polynomial time algorithm for finding a minimum cardinality safe set for the class of tournaments in which the largest strong component has size at most log<sup>1+ϵ</sup>(n). We also discuss bounds on the cardinality of safe sets in tournaments.

DOI： 10.1016/j.dam.2023.12.012

Collecting Balls on a Line by Robots with Limited Energy

Hanaka, T; Droguett, NH; Kurita, K; Ono, H; Otachi, Y

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E107.D 巻 ( 3 ) 頁： 325 - 327 2024年3月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：一般社団法人電子情報通信学会

In this paper, we study Ball Collecting with Limited Energy, which is a problem of scheduling robots with limited energy confined to a line to catch moving balls that eventually cross the line. For this problem, we show the NP-completeness of the general case and some algorithmic results for some cases with a small number of robots.

DOI： 10.1587/transinf.2023fcl0003

On a Spectral Lower Bound of Treewidth

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

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E107.D 巻 ( 3 ) 頁： 328 - 330 2024年3月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：一般社団法人電子情報通信学会

In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].

DOI： 10.1587/transinf.2023fcl0002

On the Computational Complexity of Generalized Common Shape Puzzles

Banbara, M; Minato, S; Ono, H; Uehara, R

SOFSEM 2024: THEORY AND PRACTICE OF COMPUTER SCIENCE 14519 巻頁： 55 - 68 2024年

掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics

In this study, we investigate the computational complexity of some variants of generalized puzzles. We are provided with two sets S<inf>1</inf> and S<inf>2</inf> of polyominoes. The first puzzle asks us to form the same shape using polyominoes in S<inf>1</inf> and S<inf>2</inf>. We demonstrate that this is polynomial-time solvable if S<inf>1</inf> and S<inf>2</inf> have constant numbers of polyominoes, and it is strongly NP-complete in general. The second puzzle allows us to make copies of the pieces in S<inf>1</inf> and S<inf>2</inf>. That is, a polyomino in S<inf>1</inf> can be used multiple times to form a shape. This is a generalized version of the classical puzzle known as the common multiple shape puzzle. For two polyominoes P and Q, the common multiple shape is a shape that can be formed by many copies of P and many copies of Q. We show that the second puzzle is undecidable in general. The undecidability is demonstrated by a reduction from a new type of undecidable puzzle based on tiling. Nevertheless, certain concrete instances of the common multiple shape can be solved in a practical time. We present a method for determining the common multiple shape for provided tuples of polyominoes and outline concrete results, which improve on the previously known results in the puzzle community.

DOI： 10.1007/978-3-031-52113-3_4

その他リンク： https://dblp.uni-trier.de/db/conf/sofsem/sofsem2024.html#BanbaraMOU24

　前のページ - 次のページ　

1
2
3
4
5
6
7
8
9
10
11
12
13