研究者詳細 - 小野　廣隆

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

Structural parameterizations of vertex integrity 査読有り Open Access

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

THEORETICAL COMPUTER SCIENCE 1024 巻 2025年1月

記述言語：英語出版者・発行元：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

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

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) 15538 LNCS 巻頁： 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(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

Algorithms for Optimally Shifting Intervals Under Intersection Graph Models 査読有り

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) 14752 LNCS 巻頁： 66 - 78 2025年

担当区分：最終著者記述言語：英語出版者・発行元：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

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Koki Suetsugu, Kanae Yoshiwatari: Computational complexity of Turning Tiles 査読有り

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

International Journal of Game Theory 53 巻 ( 4 ) 2024年10月

Polynomial-time equivalences and refined algorithms for longest common subsequence variants 査読有り Open Access

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

DISCRETE APPLIED MATHEMATICS 353 巻頁： 44 - 64 2024年8月

記述言語：英語出版者・発行元：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

Grouped domination parameterized by vertex cover, twin cover, and beyond 査読有り Open Access

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

THEORETICAL COMPUTER SCIENCE 996 巻 2024年5月

記述言語：英語出版者・発行元：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

Winner Determination Algorithms for Graph Games with Matching Structures

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

ALGORITHMICA 86 巻 ( 3 ) 頁： 808 - 824 2024年3月

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

Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a matching. In this paper, we define a generalized game called Colored Arc Kayles, which includes these games. Colored Arc Kayles is played on a graph whose edges are colored in black, white, or gray, and black (resp., white) edges can be selected only by the black (resp., white) player, while gray edges can be selected by both black and white players. We first observe that the winner determination for Colored Arc Kayles can be done in O∗(2n) time by a simple algorithm, where n is the order of the input graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are solved in time O∗(1.4143τ2+3.17τ), O∗(1.3161τ2+4τ), and O∗(1.1893τ2+6.34τ), respectively, where τ is the vertex cover number. Furthermore, we present an O∗((n/ν+1)ν)-time algorithm for Arc Kayles, where ν is neighborhood diversity. We finally show that Arc Kayles on trees can be solved in O∗(2n/2)(=O(1.4143n)) time, which improves O∗(3n/3)(=O(1.4423n)) by a direct adjustment of the analysis of Bodlaender et al.’s O∗(3n/3)-time algorithm for Node Kayles.

DOI： 10.1007/s00453-023-01136-w

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

Horiyama T., Kobayashi Y., Ono H., Seto K., Suzuki R.

Proceedings of the AAAI Conference on Artificial Intelligence 38 巻 ( 18 ) 頁： 20726 - 20734 2024年

掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Proceedings of the AAAI Conference on Artificial Intelligence

The uniqueness of an optimal solution to a combinatorial optimization problem attracts many fields of researchers’ attention because it has a wide range of applications, it is related to important classes in computational complexity, and an instance with only one solution is often critical for algorithm designs in theory. However, as the authors know, there is no major benchmark set consisting of only instances with unique solutions, and no algorithm generating instances with unique solutions is known; a systematic approach to getting a problem instance guaranteed having a unique solution would be helpful. A possible approach is as follows: Given a problem instance, we specify a small part of a solution in advance so that only one optimal solution meets the specification. This paper formulates such a “pre-assignment” approach for the vertex cover problem as a typical combinatorial optimization problem and discusses its computational complexity. First, we show that the problem is ΣP2 -complete in general, while the problem becomes NP-complete when an input graph is bipartite. We then present an O(2.1996n)-time algorithm for general graphs and an O(1.9181n)-time algorithm for bipartite graphs, where n is the number of vertices. The latter is based on an FPT algorithm with O∗(3.6791τ) time for vertex cover number τ. Furthermore, we show that the problem for trees can be solved in O(1.4143n) time.

DOI： 10.1609/aaai.v38i18.30060

Faster Winner Determination Algorithms for (Colored) Arc Kayles

その他リンク： https://dblp.uni-trier.de/db/conf/aaai/aaai2024.html#HoriyamaK0SS24

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

SOFSEM 2024: THEORY AND PRACTICE OF COMPUTER SCIENCE 14519 巻頁： 297 - 310 2024年

出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Arc Kayles and Colored Arc Kayles, two-player games on a graph, are generalized versions of well-studied combinatorial games Cram and Domineering, respectively. In Arc Kayles, 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, while 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 τ is the vertex cover number and 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 the winner determination Arc Kayles on a tree can be solved in O(1.3831n) time, which improves the best-known running time 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.1007/978-3-031-52113-3_21

Structural Parameterizations of Vertex Integrity [Best Paper]

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

WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2024 14549 巻頁： 406 - 420 2024年

出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI： 10.1007/978-981-97-0566-5_29

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

International Journal of Networking and Computing 14 巻 ( 1 ) 頁： 26 - 39 2024年

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

Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

International Journal of Networking and Computing 14 巻 ( 1 ) 頁： 26 - 39 2024年

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

Ono, H; Yamanaka, H

DISCRETE APPLIED MATHEMATICS 341 巻頁： 93 - 101 2023年12月

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

Given a graph G=(V,E), an L(2,1)-labeling of the graph is an assignment ℓ from the vertex set to the set of nonnegative integers such that for any pair of vertices (u,v), |ℓ(u)−ℓ(v)|≥2 if u and v are adjacent, and ℓ(u)≠ℓ(v) if u and v are at distance 2. The L(2,1)-labeling problem is to minimize the range of ℓ (i.e., maxu∈V(ℓ(u))−minu∈V(ℓ(u))+1). Although the problem is generally hard to approximate within any constant factor, it was known to be approximable within factor 10.67 for unit disk graphs. This paper designs a new way of partitioning the plane into squares for periodic labeling, based on which we present an 8-approximation polynomial-time algorithm for L(2,1)-labeling of unit disk graphs.

DOI： 10.1016/j.dam.2023.07.012

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

Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama

IPDPS Workshops 2023 abs/2303.01290 巻 2023年5月

Sequentially Swapping Tokens: Further on Graph Classes

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

SOFSEM 2023: THEORY AND PRACTICE OF COMPUTER SCIENCE 13878 巻頁： 222 - 235 2023年

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

We study the following variant of the 15 puzzle. Given a graph and two token placements on the vertices, we want 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 as Sequential Token Swapping 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 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.1007/978-3-031-23101-8_15

Shortest Beer Path Queries Based on Graph Decomposition

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

Approximation Algorithms for the Longest Run Subsequence Problem. 査読有り

小野廣隆

Leibniz International Proceedings in Informatics (LIPIcs) 259 巻 2023年

Hanaka T., Ono H., Sadakane K., Sugiyama K.

Leibniz International Proceedings in Informatics, LIPIcs 283 巻頁： 37 - 20 2023年

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

Given a directed edge-weighted graph G = (V, E) with beer vertices B ⊆ V , a beer path between two vertices u and v is a path between u and v that visits at least one beer vertex in B, and the beer distance between two vertices is the shortest length of beer paths. We consider indexing problems on beer paths, that is, a graph is given a priori, and we construct some data structures (called indexes) for the graph. Then later, we are given two vertices, and we find the beer distance or beer path between them using the data structure. For such a scheme, efficient algorithms using indexes for the beer distance and beer path queries have been proposed for outerplanar graphs and interval graphs. For example, Bacic et al. (2021) present indexes with size O(n) for outerplanar graphs and an algorithm using them that answers the beer distance between given two vertices in O(α(n)) time, where α(·) is the inverse Ackermann function; the performance is shown to be optimal. This paper proposes indexing data structures and algorithms for beer path queries on general graphs based on two types of graph decomposition: the tree decomposition and the triconnected component decomposition. We propose indexes with size O(m + nr2) based on the triconnected component decomposition, where r is the size of the largest triconnected component. For a given query u, v ∈ V , our algorithm using the indexes can output the beer distance in query time O(α(m)). In particular, our indexing data structures and algorithms achieve the optimal performance (the space and the query time) for series-parallel graphs, which is a wider class of outerplanar graphs.

DOI： 10.4230/LIPIcs.ISAAC.2023.37

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

その他リンク： https://dblp.uni-trier.de/db/conf/isaac/isaac2023.html#HanakaOSS23

Hanaka, T; Ono, H; Sugiyama, K

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

出版者・発行元：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

The existence of a pure Nash equilibrium in the two-player competitive diffusion game on graphs having chordality

Fukuzono Naoka, Hanaka Tesshu, Kiya Hironori, Ono Hirotaka

DISCRETE APPLIED MATHEMATICS 321 巻頁： 281 - 294 2022年11月

記述言語：日本語出版者・発行元：Discrete Applied Mathematics

The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon et al. (2010). It models the diffusion process of information in social networks where several competitive companies want to spread their information, for example. The nature of this game strongly depends on the graph topology, and the relationship is studied from several aspects. In this paper, we investigate the existence of a pure Nash equilibrium of the two-player competitive diffusion game on chordal and its related graphs. We show that a pure Nash equilibrium always exists on split graphs, block graphs, and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that a pure Nash equilibrium does not always exist on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found.

DOI： 10.1016/j.dam.2022.04.025

Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants

Asahiro Y., Jansson J., Lin G., Miyano E., Ono H., Utashima T.

Leibniz International Proceedings in Informatics, LIPIcs 223 巻 2022年6月

記述言語：日本語出版者・発行元：Leibniz International Proceedings in Informatics, LIPIcs

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 paper, we study four variants of LCS: the Repetition-Bounded Longest Common Subsequence problem (RBLCS) [2], the Multiset-Restricted Common Subsequence problem (MRCS) [11], the Two-Side-Filled Longest Common Subsequence problem (2FLCS), and the One-Side-Filled Longest Common Subsequence problem (1FLCS) [5, 6]. 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 [2], where the two input sequences have lengths n and poly(n). 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.4230/LIPIcs.CPM.2022.15

Capacitated Network Design Games on a Generalized Fair Allocation Model

Hanaka T., Hirose T., Ono H.

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 3 巻頁： 1616 - 1617 2022年

記述言語：日本語出版者・発行元：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

The cost-sharing connection game is a variant of routing games on a network. In this model, given a directed graph with edge costs and capacities, each agent wants to construct a path from a source to a sink with low cost. The cost of each edge is shared by the users based on a cost-sharing function. One of simple cost-sharing functions is defined as the cost divided by the number of users. It models an ideal setting, where no overhead arises when people share things, though it might be quite rare in real life. In this paper, we model more realistic scenarios of cost-sharing connection games by generalizing the cost-sharing function. The arguments do not depend on specific cost-sharing functions and are applicable for a class of all natural cost-sharing scenarios, which include equal divisions with any natural functional overheads. We show that many bounds of the Price of Anarchy and the Price of Stability under sum-cost and max-cost criteria inherit the no-overhead case.

Fair Ride Allocation on a Line

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13584 LNCS 巻頁： 421 - 435 2022年

記述言語：日本語出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Airport problem is a classical and well-known model of fair cost-sharing for a single facility among multiple agents. This paper extends it to the so-called assignment setting, that is, for multiple facilities and agents, each agent chooses a facility to use and shares the cost with the other agents. Such a situation can be often seen in sharing economy, such as sharing fees for office desks among workers, and taxi fare among customers of possibly different destinations on a line. Our model is regarded as a coalition formation game, based on the fair cost-sharing of the airport problem; we call our model a fair ride allocation on a line. As the criteria of solution concepts, we incorporate Nash stability and envy-freeness into our setting. We show that a Nash-stable feasible allocation that minimizes the social cost of agents can be computed efficiently if a feasible allocation exists. For envy-freeness, we provide several structural properties of envy-free allocations. Based on these, 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 the NP-hardness of determining the existence of an allocation under two relaxed envy-free concepts.

DOI： 10.1007/978-3-031-15714-1_24

Computing L(p, 1)-Labeling with Combined Parameters

Hanaka T., Kawai K., Ono H.

Journal of Graph Algorithms and Applications 26 巻 ( 2 ) 頁： 241 - 255 2022年

記述言語：日本語出版者・発行元：Journal of Graph Algorithms and Applications

Given a graph, an L(p, 1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices u and v, |f(u) − f(v)| ≥ p if u and v are adjacent, and f(u) ≠ f(v) if u and v are at distance 2. The L(p, 1)-labeling problem is to minimize the span of f (i.e.,maxu∈V (f(u)) − minu∈V (f(u)) + 1). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p, 1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.

DOI： 10.7155/jgaa.00592

Reallocation Problems with Minimum Completion Time

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

COMPUTING AND COMBINATORICS, COCOON 2022 13595 巻頁： 292 - 304 2022年

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/978-3-031-22105-7_26

その他リンク： https://dblp.uni-trier.de/db/conf/cocoon/cocoon2022.html#IshiiKMO22

コンピュテーション研究会　近況報告

増澤利光, 小野廣隆, 安藤映, 大下福仁

情報・システムソサイエティ誌 26 巻 ( 2 ) 頁： 10 - 11 2021年8月

Staging of astrocytopathy and complement activation in neuromyelitis optica spectrum disorders Open Access

Takai Y., Misu T., Suzuki H., Takahashi T., Okada H., Tanaka S., Okita K., Sasou S., Watanabe M., Namatame C., Matsumoto Y., Ono H., Kaneko K., Nishiyama S., Kuroda H., Nakashima I., Lassmann H., Fujihara K., Itoyama Y., Aoki M.

Brain 144 巻 ( 8 ) 頁： 2401 - 2415 2021年8月

出版者・発行元：Brain

Aquaporin 4 (AQP4)-IgG-positive neuromyelitis optica spectrum disorder (AQP4-IgG+NMOSD) is an autoimmune astrocytopathic disease pathologically characterized by the massive destruction and regeneration of astrocytes with diverse types of tissue injury with or without complement deposition. However, it is unknown whether this diversity is derived from differences in pathological processes or temporal changes. Furthermore, unlike for the demyelinating lesions in multiple sclerosis, there has been no staging of astrocytopathy in AQP4-IgG+NMOSD based on astrocyte morphology. Therefore, we classified astrocytopathy of the disease by comparing the characteristic features, such as AQP4 loss, inflammatory cell infiltration, complement deposition and demyelination activity, with the clinical phase. We performed histopathological analyses in eight autopsied cases of AQP4-IgG+NMOSD. Cases comprised six females and two males, with a median age of 56.5 years (range, 46-71 years) and a median disease duration of 62.5 months (range, 0.6-252 months). Astrocytopathy in AQP4-IgG+NMOSD was classified into the following four stages defined by the astrocyte morphology and immunoreactivity for GFAP: (i) astrocyte lysis: extensive loss of astrocytes with fragmented and/or dust-like particles; (ii) progenitor recruitment: loss of astrocytes except small nucleated cells with GFAP-positive fibre-forming foot processes; (iii) protoplasmic gliosis: presence of star-shaped astrocytes with abundant GFAP-reactive cytoplasm; and (iv) fibrous gliosis: lesions composed of densely packed mature astrocytes. The astrocyte lysis and progenitor recruitment stages dominated in clinically acute cases (within 2 months after the last recurrence). Findings common to both stages were the loss of AQP4, a decreased number of oligodendrocytes, the selective loss of myelin-associated glycoprotein and active demyelination with phagocytic macrophages. The infiltration of polymorphonuclear cells and T cells (CD4-dominant) and the deposition of activated complement (C9neo), which reflects the membrane attack complex, a hallmark of acute NMOSD lesions, were selectively observed in the astrocyte lysis stage (98.4% in astrocyte lysis, 1.6% in progenitor recruitment, and 0% in protoplasmic gliosis and fibrous gliosis). Although most of the protoplasmic gliosis and fibrous gliosis lesions were accompanied by inactive demyelinated lesions with a low amount of inflammatory cell infiltration, the deposition of complement degradation product (C3d) was observed in all four stages, even in fibrous gliosis lesions, suggesting the past or chronic occurrence of complement activation, which is a useful finding to distinguish chronic lesions in NMOSD from those in multiple sclerosis. Our staging of astrocytopathy is expected to be useful for understanding the unique temporal pathology of AQP4-IgG+NMOSD.

DOI： 10.1093/brain/awab102

Hedonic seat arrangement problems

Bodlaender H.L., Hanaka T., Jaffke L., Ono H., Otachi Y., van der Zanden T.C.

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020-May 巻頁： 1777 - 1779 2020年

記述言語：日本語出版者・発行元：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

In this paper, we study a variant of hedonic games, called Seat Arrangement. The model is defined by a bijection from agents with preferences to vertices in a graph. The utility of an agent depends on the neighbors in the graph. In this paper, we study the price of stability and fairness in Seat Arrangement, and the computational complexity and the parameterized complexity of finding certain “good” seat arrangements, say Maximum Welfare Arrangement, Maximin Utility Arrangement, Stable Arrangement, and Envy-free Arrangement.

Fair Ride Allocation on a Line

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

小野廣隆

Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems - 巻頁： 1777 - 1779 2020年

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

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

Fair Ride Allocation on a Line 査読有り

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

ACM Transactions on Economics and Computation 2025年2月

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

Safe sets and in-dominating sets in digraphs

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

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 log1+ϵ(n). We also discuss bounds on the cardinality of safe sets in tournaments.

DOI： 10.1016/j.dam.2023.12.012

On the Computational Complexity of Generalized Common Shape Puzzles

Collecting Balls on a Line by Robots with Limited Energy Open Access

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

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

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

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

In this study, we investigate the computational complexity of some variants of generalized puzzles. We are provided with two sets S1 and S2 of polyominoes. The first puzzle asks us to form the same shape using polyominoes in S1 and S2. We demonstrate that this is polynomial-time solvable if S1 and S2 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 S1 and S2. That is, a polyomino in S1 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

Shortest Longest-Path Graph Orientations

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

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 14422 LNCS 巻頁： 141 - 154 2024年

We consider a graph orientation problem that can be viewed as a generalization of Minimum Graph Coloring. Our problem takes as input an undirected graph G= (V, E) in which every edge { u, v} ∈ E has two (potentially different and not necessarily positive) weights representing the lengths of its two possible directions (u, v) and (v, u), and asks for an orientation, i.e., an assignment of a direction to each edge of G, such that the length of a longest simple directed path in the resulting directed graph is minimized. A longest path in a graph is not always a maximal path when some edges have negative lengths, so the problem has two variants depending on whether all simple directed paths or maximal simple directed paths only are taken into account in the definition. We prove that the problems are NP-hard to approximate even if restricted to subcubic planar graphs, and develop fast polynomial-time algorithms for both problem variants for three classes of graphs: path graphs, cycle graphs, and star graphs.

DOI： 10.1007/978-3-031-49190-0_10

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

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

COMBINATORIAL ALGORITHMS, IWOCA 2024 14764 巻頁： 232 - 246 2024年

An improved spectral lower bound of treewidth.

Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono 0001, Yota Otachi

CoRR abs/2404.08520 巻 2024年

Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-Like Graphs

Hanaka T., Ikeyama A., Ono H.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 14461 LNCS 巻頁： 392 - 405 2023年12月

担当区分：責任著者出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Fractional hedonic games are coalition formation games where the utility of a player is determined by the average value they assign to the members of their coalition. These games are a variation of graph hedonic games, which are a class of coalition formation games that can be succinctly represented. Due to their applicability in network clustering and their relationship to graph hedonic games, fractional hedonic games have been extensively studied from various perspectives. However, finding welfare-maximizing partitions in fractional hedonic games is a challenging task due to the nonlinearity of utilities. In fact, it has been proven to be NP-hard in general and can be solved in polynomial time only for a limited number of graph classes, such as trees. This paper presents (pseudo)polynomial-time algorithms to compute welfare-maximizing partitions in fractional hedonic games on tree-like graphs. We consider two types of social welfare measures: utilitarian and egalitarian. Tree-like graphs refer to graphs with bounded treewidth and block graphs. An NP-hardness result demonstrates that the pseudopolynomial-time solvability is the best possible under the assumption P ≠ NP.

DOI： 10.1007/978-3-031-49611-0_28

Reconfiguration of cliques in a graph Open Access

Ito, T; Ono, H; Otachi, Y

DISCRETE APPLIED MATHEMATICS 333 巻頁： 43 - 58 2023年7月

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

We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques from the viewpoint of polynomial-time solvability. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. Furthermore, we show that the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs.

DOI： 10.1016/j.dam.2023.01.026

Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13898 巻頁： 263 - 277 2023年4月

掲載種別：論文集(書籍)内論文出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A dominating set S of graph G is called an r-grouped domR such that the size of each unit is r and the subgraph of G induced by 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 , paired dominating sets), and connected dominating sets (r is arbitrary and . 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 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 This fixed-parameter tractability is good news, but the running time is not practical. We then design an -time algorithm for general 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., we can speed up the algorithm, whose running time becomes We further argue the relationship between FPT results and graph parameters, which draws the parameterized complexity landscape of r -Grouped Dominating Set.

DOI： 10.1007/978-3-031-30448-4_19

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

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

CoRR abs/2312.10599 巻 2023年

On the Computational Complexity of Generalized Common Shape Puzzles.

Mutsunori Banbara, Shin-ichi Minato, Hirotaka Ono, Ryuhei Uehara

CoRR abs/2305.10749 巻 2023年

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints.

Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono

CoRR abs/2308.16426 巻 2023年

Approximation Algorithms for the Longest Run Subsequence Problem

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

Leibniz International Proceedings in Informatics, LIPIcs 259 巻頁： 2 - 12 2023年

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

We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s1 · · · sn over an alphabet Σ, a run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S′ of S is a sequence in which every symbol σ ∈ Σ occurs in at most one run. Given a string S, the goal of LRS is to find a longest run subsequence S∗ of S such that the length |S∗| is maximized over all the run subsequences of S. It is known that LRS is APX-hard even if each symbol has at most two occurrences in the input string, and that LRS admits a polynomial-time k-approximation algorithm if the number of occurrences of every symbol in the input string is bounded by k. In this paper, we design a polynomial-time k+1/2-approximation algorithm for LRS under the k-occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 2/3 to 4/3.

DOI： 10.4230/LIPIcs.CPM.2023.2

Shortest Beer Path Queries based on Graph Decomposition.

その他リンク： https://dblp.uni-trier.de/db/conf/cpm/cpm2023.html#AsahiroEG0LMOT23

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

CoRR abs/2307.02787 巻 2023年

Turning Tiles is PSPACE-complete.

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

CoRR abs/2310.01983 巻 2023年

Parameterized Complexity of (A, l)-Path Packing 査読有り Open Access

Belmonte, R; Hanaka, T; Kanzaki, M; Kiyomi, M; Kobayashi, Y; Kobayashi, Y; Lampis, M; Ono, H; Otachi, Y

ALGORITHMICA 84 巻 ( 4 ) 頁： 871 - 895 2022年4月

記述言語：英語掲載種別：研究論文（研究会，シンポジウム資料等）出版者・発行元：Algorithmica

Given a graph G= (V, E) , A⊆ V, and integers k and ℓ, the (A, ℓ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly ℓ that have endpoints in A and internal points in V\ A. We study the parameterized complexity of this problem with parameters |A|, ℓ, k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when ℓ≤ 3 , while it is NP-complete for constant ℓ≥ 4. We also show that the problem is W[1]-hard parameterized by pathwidth+ | A| , while it is fixed-parameter tractable parameterized by treewidth+ ℓ. Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at mostℓ. We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or ℓ is a constant.

DOI： 10.1007/s00453-021-00875-y

Upper and lower degree-constrained graph orientation with minimum penalty 査読有り Open Access

Asahiro, Y; Jansson, J; Miyano, E; Ono, H

THEORETICAL COMPUTER SCIENCE 900 巻頁： 53 - 78 2022年1月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Theoretical Computer Science

In the degree-constrained graph orientation problem, the input is an unweighted, undirected graph G=(V,E) and nonnegative integers av and bv (with av≤bv) for each v∈V, and the objective is to assign a direction to every edge in E in such a way that for each v∈V, the number of outgoing edges in the resulting directed graph lies in the interval [av,bv]. When such an orientation does not exist, it is desirable to find an orientation that best fits the condition instead. In this paper, we consider the problem of finding an orientation that minimizes the total penalty ∑v∈Vcv, where cv is a penalty incurred whenever a vertex v violates its degree constraints. As penalty functions, convex, concave, and step functions are considered in this paper. We show that the problem with any convex penalty function can be solved in O(|E|1.5min⁡{log⁡(|E|⋅C),|E|0.5log⁡Δlog⁡|E|}) time, where Δ and C are the maximum degree and the largest magnitude of a penalty, respectively. In contrast, we show APX-hardness of the problem with step or concave functions. For trees and graphs with treewidth τ, the problem with any penalty function can be solved exactly in O(|V|log⁡Δ) time and O(τ2Δ2τ+2|V|) time, respectively. Finally, we consider the generalization of the problem to edge-weighted graphs and establish strong bounds on its inapproximability that hold even in the special case of stars. On the positive side, we can extend our algorithms for unweighted version of the problem to obtain pseudo-polynomial-time algorithms for the edge-weighted problem variant when restricted to trees and graphs with bounded treewidth. Also, we design a PTAS and a linear-time algorithm for stars with further restrictions on the degree constraints and edge weights.

DOI： 10.1016/j.tcs.2021.11.019

Winner Determination Algorithms for Graph Games with Matching Structures

構造的オラクルによる不完全情報TANHINMINのモデリング査読有り

KIYA Hironori, OHTO Katsuki, ONO Hirotaka

情報処理学会論文誌トランザクション数理モデル化と応用(Web) 15 巻 ( 1 ) 頁： 10 - 17 2022年1月

Yoshiwatari K., Kiya H., Hanaka T., Ono H.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13270 LNCS 巻頁： 509 - 522 2022年

記述言語：日本語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a matching. In this paper, we define a generalized game called Colored Arc Kayles, which includes these games. Colored Arc Kayles is played on a graph whose edges are colored in black, white, or gray, and black (resp., white) edges can be selected only by the black (resp., white) player, although gray edges can be selected by both black and white players. We first observe that the winner determination for Colored Arc Kayles can be done in O∗(2n) time by a simple algorithm, where n is the order of a graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are solved in time O∗(1.4143τ2+3.17τ), O∗(1.3161τ2+4τ), and O∗(1.1893τ2+6.34τ), respectively, where τ is the vertex cover number. Furthermore, we present an O∗((n/ ν+ 1 )ν) -time algorithm for Arc Kayles, where ν is neighborhood diversity. We finally show that Arc Kayles on trees can be solved in O∗(2n2) (= O(1. 4143n) ) time, which improves O∗(3n3) (= O(1. 4423n) ) by a direct adjustment of the analysis of Bodlaender et al.’s O∗(3n3) -time algorithm for Node Kayles.

DOI： 10.1007/978-3-031-06678-8_37

Capacitated Network Design Games on a Generalized Fair Allocation Model.

その他リンク： https://dblp.uni-trier.de/db/conf/iwoca/iwoca2022.html#YoshiwatariKHO22

Tesshu Hanaka, Toshiyuki Hirose, Hirotaka Ono

21st International Conference on Autonomous Agents and Multiagent Systems(AAMAS) 頁： 1616 - 1617 2022年

Winner Determination Algorithms for Graph Games with Matching Structures.

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Kanae Yoshiwatari

CoRR abs/2211.05307 巻 2022年

組合せゲームに対するアルゴリズム論的アプローチ

木谷裕紀, 小野廣隆

システム／制御／情報 65 巻 ( 10 ) 頁： 415 - 420 2021年10月

Computing the Winner of 2-Player TANHINMIN

Kiya Hironori, Ohto Katsuki, Ono Hirotaka

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E104.A 巻 ( 9 ) 頁： 1134 - 1141 2021年9月

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

DAIHINMIN, which means Grand Pauper, is a popular playing-card game in Japan. TANHINMIN is a simplified variant of DAIHINMIN, which was proposed by Nishino in 2007 in order to investigate the mathematical properties of DAIHINMIN. In this paper, we consider a 2-player generalized TANHINMIN, where the deck size is arbitrary n. We present a linear-time algorithm that determines which player has a winning strategy after all cards are distributed to the players.

DOI： 10.1587/transfun.2020dmp0026

Graph Orientation with Edge Modifications 査読有り国際共著 Open Access

Asahiro, Y; Jansson, J; Miyano, E; Ono, H; Sandhya, TP

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 32 巻 ( 02 ) 頁： 209 - 233 2021年2月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：International Journal of Foundations of Computer Science

The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices' resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges, H admits an orientation optimizing some objective involving the vertices' outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p-DEL-MAX, p-INS-MIN, p-INS-MAX, and p-DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

DOI： 10.1142/S012905412150012X

Computing L(p, 1)-Labeling with Combined Parameters 査読有り

Hanaka T., Kawai K., Ono H.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12635 LNCS 巻頁： 208 - 220 2021年2月

記述言語：日本語掲載種別：論文集(書籍)内論文出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Given a graph, an L(p, 1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), | f(u) - f(v) | ≥ p if u and v are adjacent, and f(u) ≠ f(v) if u and v are at distance 2. The L(p, 1)-labeling problem is to minimize the span of f (i.e., maxu∈V(f(u) ) - minu∈V(f(u) ) + 1 ). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p, 1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.

DOI： 10.1007/978-3-030-68211-8_17

Fairness norm through social networks: a simulation approach Open Access

Rifki O., Ono H.

Computational Social Networks 8 巻 ( 1 ) 2021年

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Computational Social Networks

Recently there has been an increased interest in adopting game-theoretic models to social norms. Most of these approaches are generally lacking a structure linking the local level of the ‘norm’ interaction to its global ‘social’ nature. Although numerous studies examined local-interaction games, where the emphasis is placed on neighborhood relations, regarding social network as a whole unique entity seems to be quite limited. In this paper, we conduct a series of simulation experiments to examine the effects that a network topology could have on the speed of emergence of the social norm. The emphasis is placed on the fairness norm in the ultimatum game context, by considering three network type models (Barabási–Albert, Watts–Strogatz and Erdős–Rényi) and several intrinsic topological properties.

DOI： 10.1186/s40649-021-00100-4

Reallocation Problems with Minimum Completion Time.

Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono

CoRR abs/2111.02579 巻 2021年

Graph orientation with splits 査読有り国際共著 Open Access

Asahiro, Y; Jansson, J; Miyano, E; Nikpey, H; Ono, H

THEORETICAL COMPUTER SCIENCE 844 巻頁： 16 - 25 2020年12月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Theoretical Computer Science

The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p-Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p, and study its computational complexity.

DOI： 10.1016/j.tcs.2020.07.013

Exact algorithms for the repetition-bounded longest common subsequence problem 査読有り国際共著 Open Access

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

THEORETICAL COMPUTER SCIENCE 838 巻頁： 238 - 249 2020年10月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Theoretical Computer Science

In this paper, we study exact, exponential-time algorithms for a variant of the classic LONGEST COMMON SUBSEQUENCE problem called the REPETITION-BOUNDED LONGEST COMMON SUBSEQUENCE problem (or RBLCS, for short): Let an alphabet S be a finite set of symbols and an occurrence constraint Cocc be a function Cocc:S→N, assigning an upper bound on the number of occurrences of each symbol in S. Given two sequences X and Y over the alphabet S and an occurrence constraint Cocc, the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s∈S appears at most Cocc(s) times in the obtained subsequence. The special case where Cocc(s)=1 for every symbol s∈S is known as the REPETITION-FREE LONGEST COMMON SUBSEQUENCE problem (RFLCS) and has been studied previously; e.g., in [1], Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS. However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. Without loss of generality, we will assume that |X|≤|Y| and |X|=n. In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O(1.44225n). Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O(1.44225n) for any occurrence constraint Cocc, and even less in certain special cases. In particular, for RFLCS, our DP-based algorithm runs in O(1.41422n) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances.

DOI： 10.1016/j.tcs.2020.07.042

Parameterized complexity of independent set reconfiguration problems 査読有り国際共著

Ito Takehiro, Kaminski Marcin, Ono Hirotaka, Suzuki Akira, Uehara Ryuhei, Yamanaka Katsuhisa

DISCRETE APPLIED MATHEMATICS 283 巻頁： 336 - 345 2020年9月

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

Suppose that we are given two independent sets I0 and Ir of a graph such that |I0|=|Ir|, and imagine that a token is placed on each vertex in I0. Then, the TOKEN JUMPING problem is to determine whether there exists a sequence of independent sets which transforms I0 into Ir so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is PSPACE-complete even for planar graphs with maximum degree three. In this paper, we first show that the problem is W[1]-hard when parameterized only by the number of tokens. We then give an FPT algorithm for general graphs when parameterized by both the number of tokens and the maximum degree. Our FPT algorithm can be modified so that it finds an actual sequence of independent sets between I0 and Ir with the minimum number of token movements. We finally show that one of the results for TOKEN JUMPING can be extended to a more generalized reconfiguration problem for independent sets, called TOKEN ADDITION AND REMOVAL.

DOI： 10.1016/j.dam.2020.01.022

Independent Set Reconfiguration Parameterized by Modular-Width 査読有り

Belmonte, R; Hanaka, T; Lampis, M; Ono, H; Otachi, Y

ALGORITHMICA 82 巻 ( 9 ) 頁： 2586 - 2605 2020年9月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Algorithmica

Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for graphs of bounded bandwidth. This fact rules out the tractability of parameterizations by most well-studied structural parameters as most of them generalize bandwidth. In this paper, we study the parameterization by modular-width, which is not comparable with bandwidth. We show that the problem parameterized by modular-width is fixed-parameter tractable under all previously studied rules TAR, TJ, and TS. The result under TAR resolves an open problem posed by Bonsma (J Graph Theory 83(2):164–195, 2016).

DOI： 10.1007/s00453-020-00700-y

その他リンク： http://link.springer.com/article/10.1007/s00453-020-00700-y/fulltext.html

Parameterized Complexity of (A,l)-Path Packing 査読有り国際共著

Belmonte R., Hanaka T., Kanzaki M., Kiyomi M., Kobayashi Y., Kobayashi Y., Lampis M., Ono H., Otachi Y.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12126 LNCS 巻頁： 43 - 55 2020年6月

Given a graph G = (V, E), (Formula Presented), and integers k and ℓ, the (A, ℓ)-Path Packing problem asks to find k vertex-disjoint paths of length ℓ that have endpoints in A and internal points in V \ A. We study the parameterized complexity of this problem with parameters |A|, ℓ, k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when ℓ ≤ 3, while it is NP-complete for constant ℓ ≥ 4. We also show that the problem is W[1]-hard parameterized by pathwidth+|A|, while it is fixed-parameter tractable parameterized by treewidth + ℓ.

DOI： 10.1007/978-3-030-48966-3_4

Parameterized complexity of safe set 査読有り国際共著

Belmonte R., Hanaka T., Katsikarelis I., Lampis M., Ono H., Otachi Y.

Journal of Graph Algorithms and Applications 24 巻 ( 3 ) 頁： 215 - 245 2020年4月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Journal of Graph Algorithms and Applications

In this paper we study the problem of finding a small safe set S in a graph G, i.e., a non-empty set of vertices such that no connected component of G[S] is adjacent to a larger component in G − S. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth pw and cannot be solved in time no(pw) unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number vc unless PH = Σp but (3) it is fixed-parameter tractable (FPT) when parameterized by3,the neighborhood diversity nd, and (4) it can be solved in time nf(cw) for some double exponential function f where cw is the clique-width. We also present (5) a faster fixed-parameter algorithm when parameterized by the solution size.

DOI： 10.7155/jgaa.00528

Space-Efficient Algorithms for Longest Increasing Subsequence 査読有り国際共著

Kiyomi, M; Ono, H; Otachi, Y; Schweitzer, P; Tarui, J

THEORY OF COMPUTING SYSTEMS 64 巻 ( 3 ) 頁： 522 - 541 2020年4月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Theory of Computing Systems

Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O(nlog n) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n≤s≤n, we present algorithms that use O(slog n) bits and O(1s⋅n2⋅logn) time for computing the length of a longest increasing subsequence, and O(1s⋅n2⋅log2n) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.

DOI： 10.1007/s00224-018-09908-6

その他リンク： http://link.springer.com/article/10.1007/s00224-018-09908-6/fulltext.html

Hedonic Seat Arrangement Problems. 査読有り国際誌

Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems 頁： 1777 - 1779 2020年

The computational complexity of the gear placement problem Open Access

Hama, VMF; Kanazawa, S; Hu, Y; Imahori, S; Ono, H; Yagiura, M

JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING 14 巻 ( 5 ) 頁： JAMDSM0069 - JAMDSM0069 2020年

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：一般社団法人日本機械学会

In this paper, we analyze the complexity of the gear placement problem (GPP). In the GPP, we are given a rectangular plane, called a gearbox, on which a torque generator source and a set of gears, called target gears, are placed. The task is to find a placement of a set of gears called sub-gears, to connect every target gear to the torque generator source so that every target gear rotates in a given direction. The objective is to minimize the number of sub-gears to be used. We prove that the GPP is NP-hard by giving a reduction from the Hamiltonian path problem on 3-regular planar graphs, which is known to be NP-complete, to the GPP. We also present an upper bound for the number of sub-gears to be placed.

DOI： 10.1299/jamdsm.2020jamdsm0069

Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium 査読有り

Fukuzono Naoka, Hanaka Tesshu, Kiya Hironori, Ono Hirotaka, Yamaguchi Ryogo

SOFSEM 2020: THEORY AND PRACTICE OF COMPUTER SCIENCE 12011 巻頁： 627 - 635 2020年

The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon et al. (2010). In the model, a player chooses an initial vertex of the graph, from which information by the player spreads through the edges connected with the initial vertex. If a vertex that is not yet influenced by any information receives information by a player, it is influenced by the information and it diffuses it to adjacent vertices. A vertex that simultaneously receives two or more types of information does not diffuse any type of information from then on. The objective of a player is to maximize the number of vertices influenced by the player’s information. In this paper, we investigate the existence of a pure Nash equilibrium of the two-player competitive diffusion game on chordal and its related graphs. We show that a pure Nash equilibrium always exists on block graphs, split graphs and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that there is an instance with no pure Nash equilibrium on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found.

DOI： 10.1007/978-3-030-38919-2_52