Group Activity Selection on Graphs: Parameterized Analysis

In varied real-life situations, ranging from carpooling to workload delegation, several activities are to be performed, to which end each activity should be assigned to a group of agents. These situations are captured by the Group Activity Selection Problem (GASP). Notably, relevant relations among agents, such as acquaintanceship or physical distance, can often be modeled naturally using graphs. To exploit this modeling ability, Igarashi, Peters and Elkind [AAAI 17] introduced gGASP. Specifically, it is required that each group would correspond to a connected set of the underlying graph. In addition, to enforce the execution of the activities in practice, no individual should desire to desert its group in favor of joining another group. In other words, the assignment should be Nash stable. In this paper, we study gGASP with Nash stability (gNSGA), whose objective is to compute such an assignment. This problem is computationally hard even on such restricted topologies as paths and stars, which naturally led Igarashi, Bredereck, Peters and Elkind [AAAI 17, AAMAS 17] to the study gNSGA in the framework of parameterized complexity. We take this line of investigation forward, significantly advancing the state-of-the-art. First, we show that gNSGA is NP-hard even when merely one activity is present. In fact, this special case remains NP-hard when we further restrict the graph to have maximum degree \(\varDelta =5\). Consequently, gNSGA is not fixed-parameter tractable (FPT), or even XP, when parameterized by \(p+\varDelta \), where p is the number of activities. However, we are able to design a parameterized algorithm for gNSGA on general graphs with respect to \(p+\varDelta +t\), where t is the maximum size of a group. Finally, we develop an algorithm that solves gNSGA on graphs of bounded treewidth \(\mathbf {tw}\) in time \(4^p\cdot (n\,+\,p)^{\mathcal {O}(\mathbf {tw})}\). Here, \(\varDelta +t\) can be arbitrarily large. Along the way, we resolve several open questions regarding gNSGA.