0
$\begingroup$

Before I even attempt coming up with an efficient algorithm, I tried googling for similar problems but didn't get far, most queries mentioning "sets" in them led to some sort of Multiple subset sum or other subset construction problem. What I'm looking for is quite literally the opposite.

The problem is very straightforward:

Given a subset of a power set, I need to tell if I can reconstruct the universal set only by using disjoint subsets.

Example 1:

$x = \{1, 2, 3, 4, 5\}$

$x_s = \{\{1\}, \{2\}, \{2, 3\}, \{3, 4, 5\}\}$

$\longrightarrow$ Reconstruction possible with $\{1\}, \{2\}, \{3, 4, 5\}$.

Example 2:

$x = \{1, 2, 3, 4, 5\}$

$x_s = \{\{1, 2\}, \{2, 3\}, \{3, 4\}, \{4, 5\}, \{1, 3, 5\}, \{4\}\}$

$\longrightarrow$ Reconstruction not possible with sets such that all sets would be pairwise disjoint.

An optimal algorithm does not seem trivial at all, but I also don't believe that I am the first person to think of this type of problem. Are there any resources regarding such problems? Could it be rephrased to become some special case of Knapsack problem?

Also, since I'm only interested in whether it's possible or not to reconstruct the universal set, maybe there's some trick I am missing that could let me avoid going through the complete tree of possible unions?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ While not the same, this is somewhat similar to the set cover problem, maybe this could help? $\endgroup$
    – Nathaniel
    Sep 6, 2022 at 21:26
  • $\begingroup$ I don't understand what you mean by "reconstruct the universal set only by using disjoint subsets". Can you state this in mathematical terms? $\endgroup$
    – D.W. ♦
    Sep 6, 2022 at 22:43
  • $\begingroup$ That was part of the the problem for me, that I wasn't sure what the correct terminology was. That should also explain why I didn't find the solution myself, I wasn't aware of cover as a term. $\endgroup$
    – Mantas Kandratavičius
    Sep 7, 2022 at 6:10

1 Answer 1

Reset to default
2
$\begingroup$

It's not clear to me what your problem is (you haven't defined what you mean by "reconstruct the universal set"), but it sounds like you may be describing the exact cover problem. This problem is NP-hard, but there are (worst-case exponential-time) algorithms for it.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Indeed, reconstruct was the non-mathematical term for cover here, exact cover seems to be precisely what I was interested in. $\endgroup$
    – Mantas Kandratavičius
    Sep 7, 2022 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.