Your problem is NP-hard for $k \geq 2$$k \geq 3$ by a straight-forward reduction from exactly-1 3-SAT3-SET-COVER.
WLOG, let $\phi = c_1 \wedge c_2 \wedge \dots \wedge c_n$ be a 3-SAT formula with the $n$ variables and $n$ clauses (if the number Quick explanation: nodes of clauses is bigger/smaller, just add enough redundant variables/clauses, you need at most polynomially many). Let $S$ be the setare triplets, nodes of all variables $x_j$ and their negations $\neg x_j$ and let $T$ have for each $j$, $consistency_j$ connected to both $x_j$are set elements and $\neg x_j$, in addition to a node $c_i$ per clause,each triplet connected to all literals in that clause. $S$ has size $n$ and $T$ has size $2n$.
It's not hard to see that an algorithm solving your problem on this graph with $n$ and $2$ will find a satisfying assignment for $\phi$ with exactly one literal set to true per clause.
I do not know what you mean by the last paragraph. If an algorithm is polynomial in $E$ thenelements it must be polynomial in $n$ as wellcontains.
