NP-complete reduction proof -- graph problem
We can reduce independent set ($IS$) problem to the overarching ($OVERARCHING$) problem as follows. We reduce the instance $\langle G, k \rangle$ of IS to an instance $\langle G',S,k\rangle$ of OVERARCHING by the following reduction.

Each vertex $v_i \in V(G)$ becomes an edge $v^1_iv^2_i = e_{v_i} \in E(G')$. $G'$ will be a disconnected graph containing $|V(G)|$ edges and $2|V(G)|$ vertices. For every $v_iv_j \in E(G)$ we will add pair $(v^1_iv^2_i, v^1_jv^2_j) = (e_{v_i}, e_{v_j})$ in $S.$ If we select one of the vertices which are neighbor then we select one of the edge in the corresponding pair in the set $S$. Since all edges are disjoint in $G'$ we have absolute freedom  there in selecting any edge we want.

Then $\langle G, k \rangle$ has a $k$-size independent set if and only if $\langle G',S,k\rangle$ has a $k$-size "overarching" set $M$.

Thus $IS \leq_P OVERARCHING$, and hence $OVERARCHING$ is NP-complete.