1
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ $S^3$ means every hyperedge has 3 elements? And if so should the 3 elements be distinct? $\endgroup$
    – John Machacek
    Commented Dec 21, 2018 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
    Commented Dec 21, 2018 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
    Commented Dec 23, 2018 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
    Commented Dec 23, 2018 at 18:13
  • $\begingroup$ I see! The word "decomposition" made me think of disjoint sets. Thanks for clarifying. $\endgroup$
    – Puck Rombach
    Commented Dec 23, 2018 at 18:49

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .