  We study four NP-hard optimal seat arrangement problems [Bodlaender et al.,
2020a], which each have as input a set of n agents, where each agent has
cardinal preferences over other agents, and an n-vertex undirected graph
(called seat graph). The task is to assign each agent to a distinct vertex in
the seat graph such that either the sum of utilities or the minimum utility is
maximized, or it is envy-free or exchange-stable. Aiming at identifying hard
and easy cases, we extensively study the algorithmic complexity of the four
problems by looking into natural graph classes for the seat graph (e.g., paths,
cycles, stars, or matchings), problem-specific parameters (e.g., the number of
non-isolated vertices in the seat graph or the maximum number of agents towards
whom an agent has non-zero preferences), and preference structures (e.g.,
non-negative or symmetric preferences). For strict preferences and seat graphs
with disjoint edges and isolated vertices, we correct an error by Bodlaender et
al. [2020b] and show that finding an envy-free arrangement remains NP-hard in
this case.
