5 papers · 1 filter
Finding a HIST: Chordality, Structural Parameters, and Diameter
Tesshu Hanaka, Hironori Kiya, Hirotaka Ono
A homeomorphically irreducible spanning tree (HIST) is a spanning tree with no degree-2 vertices, serving as a structurally minimal backbone of a graph. While the existence of HIST…
(In)approximability of Maximum Minimal FVS
Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei +2
We study the approximability of the NP-complete \textsc{Maximum Minimal Feedback Vertex Set} problem. Informally, this natural problem seems to lie in an intermediate space between…
Computational Complexity of Hedonic Games on Sparse Graphs
Tesshu Hanaka, Hironori Kiya, Yasuhide Maei +1
The additively separable hedonic game (ASHG) is a model of coalition formation games on graphs. In this paper, we intensively and extensively investigate the computational complexi…
Parameterized Complexity of Safe Set
Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis +3
In this paper we study the problem of finding a small safe set in a graph , i.e. a non-empty set of vertices such that no connected component of is adjacent to a larg…
Parameterized Orientable Deletion
Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis +2
A graph is -orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most . -orientability is a well-studied concept with close…