# Is there an algorithm for this constrained Hypergraph optimization problem?

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.

• $S^3$ means every hyperedge has 3 elements? And if so should the 3 elements be distinct? – John Machacek Dec 21 '18 at 0:03
• @JohnMachacek yes, they should. also, order of elements matters and the set H can contain different orderings of the same elements. – Simon1729 Dec 21 '18 at 5:40
• Is this not the same as finding the connected components of the graph and grouping them in a balanced way? If that is the case then this is algorithmically easy. – Puck Rombach Dec 23 '18 at 14:22
• @PuckRombach the concerning hypergraph could be completely connected so the solution might not consist of connected components. Also $A_1,A_2$ do not need to be disjoint. in fact it is very likely that they share elements. – Simon1729 Dec 23 '18 at 18:13
• I see! The word "decomposition" made me think of disjoint sets. Thanks for clarifying. – Puck Rombach Dec 23 '18 at 18:49