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.

  • 1
    $\begingroup$ $S^3$ means every hyperedge has 3 elements? And if so should the 3 elements be distinct? $\endgroup$ – John Machacek Dec 21 '18 at 0:03
  • $\begingroup$ @JohnMachacek yes, they should. also, order of elements matters and the set H can contain different orderings of the same elements. $\endgroup$ – Simon1729 Dec 21 '18 at 5:40
  • $\begingroup$ 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. $\endgroup$ – Puck Rombach Dec 23 '18 at 14:22
  • $\begingroup$ @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. $\endgroup$ – Simon1729 Dec 23 '18 at 18:13
  • $\begingroup$ I see! The word "decomposition" made me think of disjoint sets. Thanks for clarifying. $\endgroup$ – Puck Rombach Dec 23 '18 at 18:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.