  We show a close connection between structural hardness for $k$-partite graphs
and tight inapproximability results for scheduling problems with precedence
constraints. Assuming a natural but nontrivial generalisation of the bipartite
structural hardness result of Bansal and Khot, we obtain a hardness of
$2-\epsilon$ for the problem of minimising the makespan for scheduling
precedence-constrained jobs with preemption on identical parallel machines.
This matches the best approximation guarantee for this problem. Assuming the
same hypothesis, we also obtain a super constant inapproximability result for
the problem of scheduling precedence-constrained jobs on related parallel
machines, making progress towards settling an open question in both lists of
ten open questions by Williamson and Shmoys, and by Schuurman and Woeginger.
  The study of structural hardness of $k$-partite graphs is of independent
interest, as it captures the intrinsic hardness for a large family of
scheduling problems. Other than the ones already mentioned, this generalisation
also implies tight inapproximability to the problem of minimising the weighted
completion time for precedence-constrained jobs on a single machine, and the
problem of minimising the makespan of precedence-constrained jobs on identical
parallel machine, and hence unifying the results of Bansal and Khot, and
Svensson, respectively.
