  This article is devoted to propose some lower and upper bounds for the
coupled-tasks scheduling problem in presence of compatibility constraints
according to classical complexity hypothesis ($\mathcal{P} \neq \mathcal{NP}$,
$\mathcal{ETH}$). Moreover, we develop an efficient polynomial-time
approximation algorithm for the specific case for which the topology describing
the compatibility constraints is a quasi split-graph.
