Assigning tasks to agents under time conflicts: a parameterized complexity approach

We consider the problem of assigning tasks to agents under time conflicts,with applications also to frequency allocations in point-to-point wirelessnetworks. In particular, we are given a set $V$ of $n$ agents, a set $E$ of $m$tasks, and $k$ different time slots. Each task can be carried out in one of the$k$ predefined time slots, and can be represented by the subset $e\subseteq E$of the involved agents. Since each agent cannot participate to more than onetask simultaneously, we must find an allocation that assigns non-overlappingtasks to each time slot. Being the number of slots limited by $k$, in generalit is not possible to executed all the possible tasks, and our aim is todetermine a solution maximizing the overall social welfare, that is the numberof executed tasks. We focus on the restriction of this problem in which thenumber of time slots is fixed to be $k=2$, and each task is performed byexactly two agents, that is $|e|=2$. In fact, even under this assumptions, theproblem is still challenging, as it remains computationally difficult. Weprovide parameterized complexity results with respect to several reasonableparameters, showing for the different cases that the problem is fixed-parametertractable or it is paraNP-hard.