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
    $\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 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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I do not understand this algorithm. Can you show an example? $\endgroup$ – Erel Segal-Halevi Sep 16 at 14:52
  • $\begingroup$ @Erel here is one, tell me it is clearer. $\endgroup$ – Optidad Sep 16 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$ – Erel Segal-Halevi 2 days ago

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.