I'm currently developing an algorithm for computing knot coloring invariants and got to the following question:

Given a set $S$ and a certain hyper-graph $H \subseteq S^3 $, find a decomposition $S = S_1 \cup S_2$ with the constraint $H \subseteq S_1^3 \cup S_2^3$ and the goal to minimize $max(|S_1|,|S_2|)$.

I would like to know whether something of that sort has already been investigated.

I've included the tag SAT because I suspect there to be a connection between this problem and SAT, but I'm not an expert so I'm sorry if this tagging is regarded as spam.