Author name cluster

Tesshu Hanaka

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Game-Theoretic and Algorithmic Analyses of Multi-Agent Routing under Crossing Costs

Tesshu Hanaka
Nikolaos Melissinos
Hirotaka Ono

This paper introduces the Multi-Agent Routing under Crossing Cost model on mixed graphs, a novel framework tailored for asynchronous settings. In our model, instead of treating conflicts as hard constraints, each agent is assigned a path, and the system is evaluated through a cost function that measures potential head-on encounters. This “crossing cost”, which is defined as the product of agents traversing an edge in opposite directions, quantifies the risk of congestion and delay in decentralized execution. Our contributions are both game-theoretic and algorithmic. We model the setting as a congestion game with a non-standard cost function, prove the existence of pure Nash equilibria, and analyze the dynamics leading to them. Equilibria can be found in polynomial time undermildconditions, whilethegeneralcaseisPLS-complete. From an optimization perspective, deciding whether a solution with zero crossing cost exists generalizes the Steiner Orientation problem, making the problem NP-complete. To address this hardness barrier, we design a suite of parameterized algorithms for minimizing crossing cost, with parameters including the number of arcs, edges, agents, and structural graph measures such as vertex cover.

PDF

MFCS Conference 2025 Conference Paper

Broadcasting Under Structural Restrictions

Yudai Egami
Tatsuya Gima
Tesshu Hanaka
Yasuaki Kobayashi
Michael Lampis
Valia Mitsou
Edouard Nemery
Yota Otachi

In the Telephone Broadcast problem we are given a graph G = (V, E) with a designated source vertex s ∈ V. Our goal is to transmit a message, which is initially known only to s, to all vertices of the graph by using a process where in each round an informed vertex may transmit the message to one of its uninformed neighbors. The optimization objective is to minimize the number of rounds. Following up on several recent works, we investigate the structurally parameterized complexity of Telephone Broadcast. In particular, we first strengthen existing NP-hardness results by showing that the problem remains NP-complete on graphs of bounded tree-depth and also on cactus graphs which are one vertex deletion away from being path forests. Motivated by this (severe) hardness, we study several other parameterizations of the problem and obtain FPT algorithms parameterized by vertex integrity (generalizing a recent FPT algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach [TCS 2024]) and by distance to clique, as well as FPT approximation algorithms parameterized by clique-cover and cluster vertex deletion. Furthermore, we obtain structural results that relate the length of the optimal broadcast protocol of a graph G with its pathwidth and tree-depth. By presenting a substantial improvement over the best previously known bound for pathwidth (Aminian, Kamali, Seyed-Javadi, and Sumedha [ICALP 2025]) we exponentially improve the approximation ratio achievable in polynomial time on graphs of bounded pathwidth from 𝒪(4^pw) to 𝒪(pw).

Details

TCS Journal 2025 Journal Article

Finding a minimum spanning tree with a small non-terminal set

Tesshu Hanaka
Yasuaki Kobayashi

In this paper, we study the problem of finding a minimum weight spanning tree that contains each vertex in a given subset V NT of vertices as an internal vertex. This problem, called Minimum Weight Non-Terminal Spanning Tree, includes s - t Hamiltonian Path as a special case, and hence it is NP-hard. In this paper, we first observe that Non-Terminal Spanning Tree, the unweighted counterpart of Minimum Weight Non-Terminal Spanning Tree, is already NP-hard on some special graph classes. Moreover, it is W[1]-hard when parameterized by clique-width. In contrast, we give a 3k-vertex kernel and O ⁎ ( 2 k ) -time algorithm, where k is the size of non-terminal set V NT. The latter algorithm can be extended to Minimum Weight Non-Terminal Spanning Tree with the restriction that each edge has a polynomially bounded integral weight. We also show that Minimum Weight Non-Terminal Spanning Tree is fixed-parameter tractable parameterized by the number of edges in the subgraph induced by the non-terminal set V NT, extending the fixed-parameter tractability of Minimum Weight Non-Terminal Spanning Tree to a more general case. Finally, we give several results for structural parameterization.

Details DOI

JAAMAS Journal 2025 Journal Article

Hedonic seat arrangement problems

Hans L. Bodlaender
Tesshu Hanaka
Tom C. van der Zanden

Abstract 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 \(\tilde{d}(G)\) and an almost tight lower bound \(\tilde{d}(G)-1/4\) of PoF, where \(\tilde{d}(G)\) 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 \(n^{O(\gamma )}\), while it cannot be solved in time \(f(\gamma )n^{o(\gamma )}\) under ETH, where n is the number of agents and \(\gamma\) 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 \(k+\gamma\), whereas it can be solved in time \(n^{O(k)}\).

Details DOI

TCS Journal 2025 Journal Article

On the complexity of list H -packing for sparse graph classes

Tatsuya Gima
Tesshu Hanaka
Yasuaki Kobayashi
Yota Otachi
Tomohito Shirai
Akira Suzuki
Yuma Tamura
Xiao Zhou

The problem of packing as many subgraphs isomorphic to some H ∈ H as possible into a graph, where H is a collection of graphs, has been well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider “list variants” of these problems: Given a graph G, an integer k, and a collection L H of subgraphs of G isomorphic to some H ∈ H, the goal is to compute k subgraphs in L H that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.

Details DOI

TCS Journal 2025 Journal Article

Structural parameterizations of vertex integrity

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

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.

Details DOI

TCS Journal 2024 Journal Article

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

Tesshu Hanaka
Hirotaka Ono
Yota Otachi
Saeki Uda

A dominating set S of graph G is called an r-grouped dominating set if S can be partitioned into S 1, S 2, …, S k such that the size of each unit S i is r and the subgraph of G induced by S i is connected. The concept of r-grouped dominating sets generalizes several well-studied variants of dominating sets with requirements for connected component sizes, such as the ordinary dominating sets ( r = 1 ), paired dominating sets ( r = 2 ), and connected dominating sets (r is arbitrary and k = 1 ). In this paper, we investigate the computational complexity of r -Grouped Dominating Set, which is the problem of deciding whether a given graph has an r-grouped dominating set with at most k units. For general r, r -Grouped Dominating Set is hard to solve in various senses because the hardness of the connected dominating set is inherited. We thus focus on the case in which r is a constant or a parameter, but we see that r -Grouped Dominating Set for every fixed r > 0 is still hard to solve. From the observations about the hardness, we consider the parameterized complexity concerning well-studied graph structural parameters. We first see that r -Grouped Dominating Set is fixed-parameter tractable for r and treewidth, which is derived from the fact that the condition of r-grouped domination for a constant r can be represented as monadic second-order logic ( MSO 2 ). 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.

Details DOI

MFCS Conference 2024 Conference Paper

Parameterized Vertex Integrity Revisited

Tesshu Hanaka
Michael Lampis
Manolis Vasilakis
Kanae Yoshiwatari

Vertex integrity is a graph parameter that measures the connectivity of a graph. Informally, its meaning is that a graph has small vertex integrity if it has a small separator whose removal disconnects the graph into connected components which are themselves also small. Graphs with low vertex integrity are very structured; this renders many hard problems tractable and has recently attracted interest in this notion from the parameterized complexity community. In this paper we revisit the NP-complete problem of computing the vertex integrity of a given graph from the point of view of structural parameterizations. We present a number of new results, which also answer some recently posed open questions from the literature. Specifically, we show that unweighted vertex integrity is W[1]-hard parameterized by treedepth; we show that the problem remains W[1]-hard if we parameterize by feedback edge set size (via a reduction from a Bin Packing variant which may be of independent interest); and complementing this we show that the problem is FPT by max-leaf number. Furthermore, for weighted vertex integrity, we show that the problem admits a single-exponential FPT algorithm parameterized by vertex cover or by modular width, the latter result improving upon a previous algorithm which required weights to be polynomially bounded.

Details

AAAI Conference 2023 Conference Paper

A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems

Tesshu Hanaka
Masashi Kiyomi
Yasuaki Kobayashi
Yusuke Kobayashi
Kazuhiro Kurita
Yota Otachi

Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world problems as objective functions and constraints are only ``approximately'' formulated for original real-world problems. To solve this issue, finding \emph{multiple} solutions is a natural direction, and diversity of solutions is an important concept in this context. Unfortunately, finding diverse solutions is much harder than finding a single solution. To cope with the difficulty, we investigate the approximability of finding diverse solutions. As a main result, we propose a framework to design approximation algorithms for finding diverse solutions, which yields several outcomes including constant-factor approximation algorithms for finding diverse matchings in graphs and diverse common bases in two matroids and PTASes for finding diverse minimum cuts and interval schedulings.

PDF Details DOI

TCS Journal 2023 Journal Article

Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144]

Yuichi Asahiro
Hiroshi Eto
Tesshu Hanaka
Guohui Lin
Eiji Miyano
Ippei Terabaru

For a graph G = ( V, E ) and a subset S ⊆ V of vertices, a vertex is happy if all its neighbor vertices in G are contained in S. Given a connected undirected graph and an integer k, the Maximum Happy Set Problem (MaxHS) asks to find a set S of k vertices which maximizes the number of happy vertices in S (note that all happy vertices in V belong to S). We proposed an algorithm for MaxHS on proper interval graphs in Theor. Comput. Sci. 866 (2021) 123–144. However, due to a wrong observation made by the authors, it works only on proper interval graphs obeying the observation. In this corrigendum, we propose a new algorithm which runs in O ( k | V | log ⁡ k + | E | ) time for proper interval graphs.

Details DOI

AAMAS Conference 2022 Conference Paper

Capacitated Network Design Games on a Generalized Fair Allocation Model

Tesshu Hanaka
Toshiyuki Hirose
Hirotaka Ono

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.

PDF

AAAI Conference 2022 Conference Paper

Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study

Tesshu Hanaka
Yasuaki Kobayashi
Kazuhiro Kurita
See Woo Lee
Yota Otachi

Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study the following type of problems: given an integer k, the problem asks for k solutions such that the sum of pairwise (weighted) Hamming distances between these solutions is maximized. Such solutions are called diverse solutions. We present a polynomial-time algorithm for finding diverse shortest stpaths in weighted directed graphs. Moreover, we study the diverse version of other classical combinatorial problems such as diverse weighted matroid bases, diverse weighted arborescences, and diverse bipartite matchings. We show that these problems can be solved in polynomial time as well. To evaluate the practical performance of our algorithm for finding diverse shortest st-paths, we conduct a computational experiment with synthetic and real-world instances. The experiment shows that our algorithm successfully computes diverse solutions within reasonable computational time.

PDF Details

TCS Journal 2022 Journal Article

Exploring the gap between treedepth and vertex cover through vertex integrity

Tatsuya Gima
Tesshu Hanaka
Masashi Kiyomi
Yasuaki Kobayashi
Yota Otachi

For problems intractable on graphs of bounded treewidth, two graph parameters treedepth and vertex cover number have been used to obtain fine-grained algorithmic and complexity results. Although the studies in this direction are successful, we still need a systematic way for further investigations because the graphs of bounded vertex cover number form a rather small subclass of graphs of bounded treedepth. To fill this gap, we use another graph parameter, vertex integrity, which is placed between the two parameters mentioned above. For several graph problems, we generalize fixed-parameter tractability results parameterized by vertex cover number to the ones parameterized by vertex integrity. We also show some finer complexity contrasts by showing hardness with respect to vertex integrity or treedepth.

Details DOI

TCS Journal 2021 Journal Article

A (probably) optimal algorithm for Bisection on bounded-treewidth graphs

Tesshu Hanaka
Yasuaki Kobayashi
Taiga Sone

The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the total weight of edges between the two sets is maximized/minimized. Although these two problems are known to be NP-hard, there is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen et al. (2005) [5] gave an O ( 2 t n 3 ) -time algorithm when given a tree decomposition of width t of the input graph, where n is the number of vertices of the input graph. Eiben et al. (2021) [10] improved the dependency of n in the running time by giving an O ( 8 t t 5 n 2 log ⁡ n ) -time algorithm. Moreover, they showed that there is no O ( n 2 − ε ) -time algorithm for trees under some reasonable complexity assumption. In this paper, we show an O ( 2 t ( t n ) 2 ) -time algorithm for both problems, which is asymptotically tight to their conditional lower bound. We also show that the exponential dependency of the treewidth is asymptotically optimal under the Strong Exponential Time Hypothesis. Finally, we discuss the (in)tractability of both problems with respect to special graph classes.

Details DOI

TCS Journal 2021 Journal Article

Complexity and approximability of the happy set problem

Yuichi Asahiro
Hiroshi Eto
Tesshu Hanaka
Guohui Lin
Eiji Miyano
Ippei Terabaru

In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G = ( V, E ) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G = ( V, E ) and an integer k, the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a ( 2 Δ + 1 ) -approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard.

Details DOI

TCS Journal 2021 Journal Article

Finding a maximum minimal separator: Graph classes and fixed-parameter tractability

Tesshu Hanaka
Yasuaki Kobayashi
Yusuke Kobayashi
Tsuyoshi Yagita

We study the problem of finding a maximum cardinality minimal separator of a graph. This problem is known to be NP-hard even for bipartite graphs. In this paper, we strengthen this hardness by showing that for planar bipartite graphs, the problem remains NP-hard. Moreover, for co-bipartite graphs and for line graphs, the problem also remains NP-hard. On the positive side, we give an algorithm deciding whether an input graph has a minimal separator of size at least k that runs in time 2 O ( k ) n O ( 1 ). We further show that there is no 2 o ( n ) n O ( 1 ) -time algorithm unless the Exponential Time Hypothesis (ETH) fails. Finally, we discuss a lower bound for polynomial kernelizations of this problem.

Details DOI

AAAI Conference 2021 Conference Paper

Finding Diverse Trees, Paths, and More

Tesshu Hanaka
Yasuaki Kobayashi
Kazuhiro Kurita
Yota Otachi

Mathematical modeling is a standard approach to solve many real-world problems and diversity of solutions is an important issue, emerging in applying solutions obtained from mathematical models to real-world problems. Many studies have been devoted to finding diverse solutions. Baste et al. (Algorithms 2019, IJCAI 2020) recently initiated the study of computing diverse solutions of combinatorial problems from the perspective of fixed-parameter tractability. They considered problems of finding r solutions that maximize some diversity measures (the minimum or sum of the pairwise Hamming distances among them) and gave some fixed-parameter tractable algorithms for the diverse version of several well-known problems, such as VERTEX COVER, FEEDBACK VERTEX SET, d-HITTING SET, and problems on bounded-treewidth graphs. In this work, we further investigate the (fixed-parameter) tractability of problems of finding diverse spanning trees, paths, and several subgraphs. In particular, we show that, given a graph G and an integer r, the problem of computing r spanning trees of G maximizing the sum of the pairwise Hamming distances among them can be solved in polynomial time. To the best of the authors’ knowledge, this is the first polynomial-time solvable case for finding diverse solutions of unbounded size.

PDF Details

TCS Journal 2020 Journal Article

Reconfiguring spanning and induced subgraphs

Tesshu Hanaka
Takehiro Ito
Haruka Mizuta
Benjamin Moore
Naomi Nishimura
Vijay Subramanya
Akira Suzuki
Krishna Vaidyanathan

Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as subgraph reconfiguration, most of the related results appear under the name of the property under consideration; for example, independent set, clique, and matching. In this paper, we systematically clarify the complexity status of subgraph reconfiguration with respect to graph structure properties.

Details DOI

TCS Journal 2019 Journal Article

On the maximum weight minimal separator

Tesshu Hanaka
Hans L. Bodlaender
Tom C. van der Zanden
Hirotaka Ono

Given an undirected and connected graph G = ( V, E ) and two vertices s, t ∈ V, a vertex subset S that separates s and t is called an s-t separator, and an s-t separator is called minimal if no proper subset of S separates s and t. Moreover, we say that a set S is a minimal separator of G if S is a minimal s-t separator for some s and t. In this paper, we consider finding a minimal (s-t) separator with maximum weight on a vertex-weighted graph. We first prove that these problems are NP-hard. On the other hand, we give an O ⁎ ( tw O ( tw ) ) -time deterministic algorithm based on tree decompositions where O ⁎ is the order notation omitting the polynomial factor of n. Moreover, we improve the algorithm by using the Rank-Based approach and the running time is O ⁎ ( 38 ⋅ 2 ω ) tw. Finally, we give an O ⁎ ( 9 tw ⋅ W 2 ) -time randomized algorithm to determine whether there exists a minimal (s-t) separator where W is its weight and tw is the treewidth of G.

Details DOI

MFCS Conference 2018 Conference Paper

New Results on Directed Edge Dominating Set

Rémy Belmonte
Tesshu Hanaka
Ioannis Katsikarelis
Eun Jung Kim 0002
Michael Lampis

We study a family of generalizations of Edge Dominating Set on directed graphs called Directed (p, q)-Edge Dominating Set. In this problem an arc (u, v) is said to dominate itself, as well as all arcs which are at distance at most q from v, or at distance at most p to u. First, we give significantly improved FPT algorithms for the two most important cases of the problem, (0, 1)-dEDS and (1, 1)-dEDS (that correspond to versions of Dominating Set on line graphs), as well as polynomial kernels. We also improve the best-known approximation for these cases from logarithmic to constant. In addition, we show that (p, q)-dEDS is FPT parameterized by p+q+tw, but W-hard parameterized just by tw, where tw is the treewidth of the underlying graph of the input. We then go on to focus on the complexity of the problem on tournaments. Here, we provide a complete classification for every possible fixed value of p, q, which shows that the problem exhibits a surprising behavior, including cases which are in P; cases which are solvable in quasi-polynomial time but not in P; and a single case (p=q=1) which is NP-hard (under randomized reductions) and cannot be solved in sub-exponential time, under standard assumptions.

Details