Farehe Soheil

Merlin de la Haye, Pascal Lenzner, Farehe Soheil et al.

Hedonic games are fundamental models for investigating the formation of coalitions among a set of strategic agents, where every agent has a certain utility for every possible coalition of agents it can be part of. To avoid the intractability of defining exponentially many utilities for all possible coalitions, many variants with succinct representations of the agents' utility functions have been devised and analyzed, e.g., modified fractional hedonic games by Monaco et al. [JAAMAS 2020]. We extend this by studying a novel succinct variant that is related to modified fractional hedonic games. In our model, each agent has a fixed type-value and an agent's cost for some given coalition is based on the differences between its value and those of the other members of its coalition. This allows to model natural situations like athletes forming training groups with similar performance levels or voters that partition themselves along a political spectrum. In particular, we investigate natural variants where an agent's cost is defined by distance thresholds, or by the maximum or average value difference to the other agents in its coalition. For these settings, we study the existence of stable coalition structures, their properties, and their quality in terms of the price of anarchy and the price of stability. Further, we investigate the impact of limiting the maximum number of coalitions. Despite the simple setting with metric distances on a line, we uncover a rich landscape of models, partially with counter-intuitive behavior. Also, our focus on both swap stability and jump stability allows us to study the influence of fixing the number and the size of the coalitions. Overall, we find that stable coalition structures always exist but that their properties and quality can vary widely.

Michelle Döring, Jan Fehse, Tobias Friedrich et al.

The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph $G$, there are $k$ vehicles available to jointly cover the set of clients $C \subseteq V(G)$. Every vehicle must start at one of the depot vertices $D \subseteq V(G)$ and return to its start. Capacitated Vehicle Routing (CVRP) additionally restricts the route of each vehicle by limiting the number of clients it can cover, the distance it can travel, or both. In this work, we study the complexity of VRP and the three variants of CVRP for several parameterizations, in particular focusing on the treewidth of $G$. We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and $W[\cdot]$-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity.

Kirill Simonov, Farehe Soheil, Shaily Verma

For a given graph $G$ and a subset of vertices $S$, a \emph{distance preserver} is a subgraph of $G$ that preserves shortest paths between the vertices of $S$. We distinguish between a \emph{subsetwise} distance preserver, which preserves distances between all pairs in $S$, and a \emph{pairwise} distance preserver, which preserves distances only between specific pairs of vertices in $S$, given in the input. While a large body of work is dedicated to upper and lower bounds on the size of distance preservers and, more generally, graph spanners, the computational complexity of finding the minimum distance preserver has received comparatively little attention. We consider the respective \scup{Subsetwise Distance Preserver}\xspace (\scup{SDP}\xspace) and \scup{Pairwise Distance Preserver}\xspace (\scup{PDP}\xspace) problems and initiate the study of their computational complexity. We provide a detailed complexity landscape with respect to natural parameters, including the number of terminals, solution size, vertex cover, and treewidth. Our main contributions are as follows: \begin{itemize} \setlength{\itemsep}{0.5em} \item Both \scup{PDP}\xspace and \scup{SDP}\xspace are \nph\ even on subgraphs of the grid. Moreover, when parameterized by the number of terminals, the problems are \wh{1}\ on subgraphs of the grid, while they become \textsc{FPT}\ on full grids. \item \scup{PDP}\xspace is \nph\ on graphs of vertex cover $3$, while \scup{SDP}\xspace is \textsc{FPT}\ when parameterized by the vertex cover of the graph. Thus, the vertex cover parameter distinguishes the two variants. \item Both problems are \textsc{FPT}\ when parameterized by the number of terminals and the treewidth of the graph. \end{itemize}