  We study large-scale systems operating under the JSQ$(d)$ policy in the
presence of stringent task-server compatibility constraints. Consider a system
with $N$ identical single-server queues and $M(N)$ task types, where each
server is able to process only a small subset of possible task types. Each
arriving task selects $d\geq 2$ random servers compatible to its type, and
joins the shortest queue among them. The compatibility constraint is naturally
captured by a fixed bipartite graph $G_N$ between the servers and the task
types. When $G_N$ is complete bipartite, the meanfield approximation is proven
to be accurate. However, such dense compatibility graphs are infeasible due to
their overwhelming implementation cost and prohibitive storage capacity
requirement at the servers. Our goal in this paper is to characterize the class
of sparse compatibility graphs for which the meanfield approximation remains
valid.
  To achieve this, first, we introduce a novel graph expansion-based notion,
called proportional sparsity, and establish that systems with proportionally
sparse compatibility graphs match the performance of a fully flexible system,
asymptotically in the large-system limit. Furthermore, for any $c(N)$
satisfying $$\frac{Nc(N)}{M(N)\ln(N)}\to \infty\quad \text{and}\quad c(N)\to
\infty,$$ as $N\to\infty$, we show that proportionally sparse random
compatibility graphs can be designed, so that the degree of each server is at
most $c(N)$. This reduces the server-degree almost by a factor $N/\ln(N)$,
compared to the complete bipartite compatibility graph, while maintaining the
same asymptotic performance. Extensive simulation experiments are conducted to
corroborate the theoretical results.
