Parameterized complexity of a coupled-task scheduling problem

In this article, we investigate the parameterized complexity of coupled-task scheduling in the presence of compatibility constraints given by a compatibility graph. In this model, each task contains two sub-tasks delayed by an idle time. Moreover, a sub-task can be performed during the idle time of another task if the two tasks are compatible. We consider a parameterized version of the scheduling problem: is there a schedule in which at least k coupled-tasks have a completion time before a fixed due date? It is known that this problem is NP-complete. We prove that it is fixed-parameter tractable (FPT) parameterized by k the standard parameter if the total duration of each task is bounded by a constant, whereas the problem becomes W[1]-hard otherwise. We also show that in the former case, the problem does not admit a polynomial kernel under some standard complexity assumptions. Moreover, we obtain an FPT algorithm when the problem is parameterized by the size of a vertex cover of the compatibility graph.