Tesshu Hanaka

Tesshu Hanaka, Airi Ikeyama, Hirotaka Ono

Fractional hedonic games are coalition formation games where a player's utility 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 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. A hardness result is provided, demonstrating that the pseudopolynomial-time solvability is the best possible under the assumption P$\neq$NP.

Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka et al.

In well-studied graph modification problems, adding and deleting vertices and edges are used as graph editing operations. We propose a model for graph modification on geometric intersection graphs called Geometric Graph Edit Distance that moves objects as an edit operation. Our results are mainly focused on interval graphs. In particular, we give a linear-time algorithm to find the minimum total moving distance to render an interval graph complete. The approach of this algorithm can be applied for: (i) rendering a unit square graph complete over the $L_1$ 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.

Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka et al.

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

Tesshu Hanaka, Daisuke Tsuru

This paper investigates the complexity of finding secluded paths in graphs. We focus on the \textsc{Short Secluded Path} problem and a natural new variant we introduce, \textsc{Shortest Secluded Path}. Formally, given an undirected graph $G=(V, E)$, two vertices $s,t\in V$, and two integers $k,l$, the \textsc{Short Secluded Path} problem asks whether there exists an $s$-$t$ path of length at most $k$ with at most $l$ neighbors. This problem is known to be computationally hard: it is W[1]-hard when parameterized by the path length $k$ or by cliquewidth, and para-NP-complete when parameterized by the number $l$ of neighbors. The fixed-parameter tractability is known for $k+l$ or treewidth. In this paper, we expand the parameterized complexity landscape by designing (1) an XP algorithm parameterized by cliquewidth and (2) fixed-parameter algorithms parameterized by neighborhood diversity and twin cover number, respectively. As a byproduct, our results also yield parameterized algorithms for the classic \textsc{$s$-$t$ $k$-Path} problem under the considered parameters. Furthermore, we introduce the \textsc{Shortest Secluded Path} problem, which seeks a shortest $s$-$t$ path with the minimum number of neighbors. In contrast to the hardness of the original problem, we reveal that this variant is solvable in polynomial time on unweighted graphs. We complete this by showing that for edge-weighted graphs, the problem becomes W[1]-hard yet remains in XP when parameterized by the shortest path distance between $s$ and $t$.

Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita et al.

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 $st$-paths 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.