3
$\begingroup$

A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family corresponds to a path from the root to a leaf. For example, the following family is treeable:

{ {1, 2, 6}, {1, 3, 4, 5, 6} }

A possible tree is:

1 -> 6 -> 2
     |
     + -> 3 -> 4 -> 5

However, the following family is not treeable:

{ {0, 1, 2}, {0, 2, 3}, {0, 3, 1} }

Is it possible to decide in polynomial time whether a given set-family is treeable (and construct a tree)?

$\endgroup$
1
  • 1
    $\begingroup$ The tree you're constructing looks a lot like a set-trie, a data structure that can be used for set containment queries on a family of sets. This report by Wermensjö and Grönvall looks at some problems related to trying to minimize the size of such a trie. $\endgroup$
    – Discrete lizard
    Sep 16 '20 at 12:29
1
$\begingroup$

An idea is to use a tree of set instead of a tree of indexes. One can develop it arbitrarily to a valid tree of indexes at end. An advantage is that you obtain all the valid trees with this process.

Let's consider the set of sets $A$ as a list $A[i]$. The initial tree $G(V, E)$ of set contains only one vertex which is the first set $root = s_0$. And you keep a set $D$ of all indexes you already encoutered.

Then, we loop on other sets to add their information to the set tree. We consider the vertices of the tree starting from the root and adding new vertices when necessary.

let s define a function compare($s$, $v$) with $s$ a set and $v$, the set associated to a vertex of $G$.

  • if $s == v$ then return true

  • $c = s \cap v$

  • if $c == v$ then

    • for $v_s$ in sons(v) if compare(s-c, $v_s$) then return true
    • if $s-c \cap D$ is not empty then return false
    • create a new son to $v$, $v_s$ associated to set $s-c$ and return True
  • in $G$, develop vertex $v$ to $v_1$ and $v_2$ associated respectively to sets $c$ and $v-c$, return compare($s$, $v_1$)

Thus, the main loop is:

  • $root = A[0]$
  • $D = A[0]$
  • for $s$ in $A[1:]$
    • if compare(s, root) then $D = D \cup s$
    • else return false
  • return true

When reaching the $i^{th}$ set, $G$ contains at most $i-1$ vertices, and you will recursively call the compare function up to $i-1$ times. Thus for $N$ sets covering $L$ different indexes (thus the set operations are $O(L)$), this algorithm solves the problem in $O(L N^2)$

An exemple: $A = [\{1, 3, 5\}, \{1, 2, 3, 4\}, \{ 1, 2, 3, 6\}, \{1, 2, 3, 5, 7\}]$

the initial tree $T$ has one vertex associated to the set $A[0] = \{1, 3, 5\}$

{1, 3, 5}

then you treat $A[1] = \{1, 2, 3, 4\}$, the root vertex has to be developed in

{1, 3} - {5}

to finally add a $\{2, 4\}$ son vertex to the root:

{1, 3} - {5}
|
{2, 4}

then comes $A[2] = \{ 1, 2, 3, 6\}$, after root, it remains $s = \{2, 6\}$. On $\{5\}$ child, there is no possibility as 2 is already in $D$. But on $\{2, 4\}$ child, it works after developing it.

{1, 3} - {5}
|
{2} - {4}
|
{6}

Finally comes $A[3] = \{1, 2, 3, 5, 7\}$, that will not work as 2 and 5 are both in $D$ and in different branches of $T$.

$\endgroup$
4
  • $\begingroup$ I do not understand this algorithm. Can you show an example? $\endgroup$ Sep 16 '20 at 14:52
  • $\begingroup$ @Erel here is one, tell me it is clearer. $\endgroup$
    – Optidad
    Sep 16 '20 at 15:21
  • $\begingroup$ Thanks for the example, now it is clearer. But, how do you know that it indeed always finds a tree when there is one - maybe the order in which you consider the sets can affect the final outcome? $\endgroup$ Nov 22 '20 at 8:54
  • $\begingroup$ @Erel For every input set you consider, you actually do the minimum modifications (development of the set tree), to make the input set "acceptable" by the set tree. Thus, the input order does not affect the output. Once again the output is still a set tree, caracterizing all the valid solutions. You can develop it abitrarily to any of them and it may not miss one. $\endgroup$
    – Optidad
    Dec 3 '20 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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