Algorithm for finding subsets subject to union condition

Question

I'm a mathematician and the following came up in my research:

Fix some positive integers $a_0,...,a_n$ and $N$.

Consider subsets $A_i \subset \{0,...,N\}$ where $|A_i|=a_i$, subject to some fixed conditions of the form: $A_{i_0}=A_{j_0}\sqcup A_{j_1}\sqcup ... \sqcup A_{j_t}$. (See an example below).

I want to code an algorithm that takes the values $a_1,...,a_n$, $N$ and the conditions $(i_0, \{j_0,...,j_t\})$, and returns all possible values for the subsets $A_1,...,A_n$.

To be clear, the condition means that $A_{i_0}$ is the union of $A_{j_0},...,A_{j_t}$ and $A_{j_k}\cap A_{j_{k'}}=\emptyset$ for all sets in the RHS.

What's a good way to go about this?

---

Example: Take $N=1$ and $a_0=a_1=a_3=a_4=1$ and $a_2=2$, subject to: $A_2=A_0\sqcup A_1$, $A_2=A_3\sqcup A_4$. There are exactly 4 such families of subsets:

• $A_0=A_3=\{0\}$, $A_1=A_4=\{1\}$, $A_2=\{0,1\}$

• $A_0=A_4=\{0\}$, $A_1=A_3=\{1\}$, $A_2=\{0,1\}$

• $A_1=A_3=\{0\}$, $A_0=A_4=\{1\}$, $A_2=\{0,1\}$

• $A_1 =A_4=\{0\}$, $A_0=A_3=\{1\}$, $A_2=\{0,1\}$

Notes: I suspect the answer is some sort of recursive function, but I haven't been able to do this by myself. I also suspect this can be translated into a graph coloring problem. Incidentally, here is the (as of yet unanswered) math version of this question

• plshelp: How big is $N$? If $N$ is around 10ドル^4$ you could solve this using a system of linear equations.
• D.W.: Is this a practical question or a theoretical one? What do you want to know? Do you want to know whether there is a polynomial-time algorithm, or do you just something that will work well enough? If you want something that will work well enough, about how large is $n,ドル $N,ドル a typical value of $a_i,ドル and the number of conditions? I suspect your problem might be NP-hard but I don't know for sure. We prefer that you not cross-post on two different SE sites.
• Alvaro Martinez: @D.W. Sorry, I thought I might get two different approaches on the two sites. On the contrary I got zero :). It's a practical question, though the faster the better. It's related to the link in my next comment. In reality $N$ can be anything, even under 20ドル$ could be insightful. By the nature of the problem, the values of the $a_i$'s are bounded above by $N$. The number of sets $n$ varies but again even under 20ドル$ would be useful. I think a recurseive approach (where I discard dead ends) may not be as hard as I thought yesterday. I'm going to try again now. Thanks for your comments
• Alvaro Martinez: arxiv.org/abs/1702.04140

Answer 1

Given your comments that the numbers involved here are all fairly small, I recommend you use a SAT solver. There is a straightforward encoding: introduce boolean variables $x_{i,\ell}$, with the intended meaning that $x_{i,\ell}$ is true iff $\ell \in A_i$. Then all of your constraints can be translated into CNF clauses, and you can search for a satisfying assignment to the resulting CNF formula using a SAT solver.

The trickiest part will be the cardinality constraints (that $|A_i|=a_i$). That can be encoded using standard methods (see, e.g., Reduce the following problem to SAT, Encoding 1-out-of-n constraint for SAT solvers). In practice, your life will be easier if you use Z3, which provides a convenient front-end to SAT solvers. Z3 supports cardinality constraints natively (see, e.g., https://stackoverflow.com/q/43081929/781723).

Any time you find yourself doing something like recursive search with backtracking etc., consider a SAT solver. At its core, that is more or less what a SAT solver is doing, but folks have worked out powerful and sophisticated methods for doing that intelligently.

---

Another approach would be to use an integer linear programming (ILP) solver. In particular, introduce zero-or-one variables $x_{i,\ell}$, with the intended meaning that $x_{i,\ell}=1$ iff $\ell \in A_i$ (the same encoding as above). Now, each constraint can be encoded into a linear inequality. Then, try to solve the resulting problem with an off-the-shelf ILP solver, such as Cplex or Gurobi.

The encoding into ILP is in some sense "simpler" than the encoding into SAT (in particular, the cardinality constraints can be encoded directly in a natural way), so it's possible this might work better.

• Alvaro Martinez: Thanks so much! This is exactly the kind of thing I was looking for, I'll give it a try.
• D.W.: @AlvaroMartinez, you're welcome. Another possible approach occurred to me (using ILP), so I added it to the bottom of my answer.
• Alvaro Martinez: When I learnt ILP in undergrad I saw it for maximization/minimization problems (I recall the simplex algorithm), but can it also be used to get all the solutions of a given set of inequalities alone?
• D.W.: @AlvaroMartinez, both SAT solvers and ILP solvers yield only a single solution, rather than all solutions, but there are ways to extract all solutions (e.g., one way is to find one solution, then add a constraint that excludes that solution and find another, and repeat; there are other methods as well).
• Alvaro Martinez: Didn't think of that, makes sense!