3

Suppose I have a a graph with 2^N - 1 nodes, numbered 1 to 2^N - 1. Node i "depends on" node j if all the bits in the binary representation of j that are 1, are also 1 in the binary representation of i. So, for instance, if N=3, then node 7 depends on all other nodes. Node 6 depends on nodes 4 and 2.

The problem is eliminating nodes. I can eliminate a node if no other nodes depend on it. No nodes depend on 7; so I can eliminate 7. After eliminating 7, I can eliminate 6, 5, and 3, etc. What I'd like is to find an efficient algorithm for listing all the possible unique elimination paths. (that is, 7-6-5 is the same as 7-5-6, so we only need to list one of the two). I have a dumb algorithm already, but I think there must be a better way.

I have three related questions:

  1. Does this problem have a general name?

  2. What's the best way to solve it?

  3. Is there a general formula for the number of unique elimination paths?

Edit: I should note that a node cannot depend on itself, by definition.

Edit2: Let S = {s_1, s_2, s_3,...,s_m} be the set of all m valid elimination paths. s_i and s_j are "equivalent" (for my purposes) iff the two eliminations s_i and s_j would lead to the same graph after elimination. I suppose to be clearer I could say that what I want is the set of all unique graphs resulting from valid elimination steps.

Edit3: Note that elimination paths may be different lengths. For N=2, the 5 valid elimination paths are (),(3),(3,2),(3,1),(3,2,1). For N=3, there are 19 unique paths.

Edit4: Re: my application - the application is in statistics. Given N factors, there are 2^N - 1 possible terms in statistical model (see http://en.wikipedia.org/wiki/Analysis_of_variance#ANOVA_for_multiple_factors) that can contain the main effects (the factors alone) and various (2,3,... way) interactions between the factors. But an interaction can only be present in a model if all sub-interactions (or main effects) are present. For three factors a, b, and c, for example, the 3 way interaction a:b:c can only be in present if all the constituent two-way interactions (a:b, a:c, b:c) are present (and likewise for the two-ways). Thus, the model a + b + c + a:b + a:b:c would not be allowed. I'm looking for a quick way to generate all valid models.

Improve this question
12
  • 1
    What can be consider as unique? 5 and 6 actually are not similar if we look at their positions in graph. Commented Jan 27, 2014 at 9:56
  • Isn't the graph a DAG and the algorithm similar to topological sort? Commented Jan 27, 2014 at 10:05
  • 1
    Also, your requirements are a bit vague. If 7-6-5 and 7-5-6 are the same, why wouldn't (imaginary paths) 7-6-5-4-3-2-1 and 7-6-4-5-3-1-2 be the same? Commented Jan 27, 2014 at 10:07
  • @Shahbaz, no, because 7-6-4-5-3-1-2 is not an elimination path. You can't eliminate 4 before 5, because 5 depends on 4. Commented Jan 27, 2014 at 10:15
  • @PhamTrung, I mean that two eliminations paths are the same if they both leave the same graph after the elimination (assuming they are both valid eliminations). Commented Jan 27, 2014 at 10:17

3 Answers 3

Reset to default
1

It seems easier to think about this in terms of sets: you are looking for families of subsets of {1, ..., N} such that for each set in the family also all its subsets are present. Each such family is determined by the inclusion-wise maximal sets, which must be overlapping. Families of pairwise overlapping sets are called Sperner families. So you are looking for Sperner families, plus the union of all the subsets in the family. Possibly known algorithms for enumerating Sperner families or antichains in general are useful; without knowing what you actually want to do with them, it's hard to tell.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

The Dedekind numbers (3,6,20) do look like the number of paths + 1 for N=1, 2, and 3. Do it looks like the answer to (3) is probably "No".
1

Thanks to @FalkHüffner's answer, I saw that what I wanted to do was equivalent to finding monotonic Boolean functions for N arguments. If you look at the figure on the Wikipedia page for Dedekind numbers (http://en.wikipedia.org/wiki/Dedekind_number) the figure expresses the problem graphically. There is an algorithm for generating monotonic Boolean functions (http://www.mathpages.com/home/kmath094.htm) and it is quite simple to construct.

For my purposes, I use the algorithm, then eliminate the first column and last row of the resulting binary arrays. Starting from the top row down, each row has a 1 in the ith column if one can eliminate the ith node.

Thanks!

Improve this answer

Comments

0

You can build a "heap", in which at depth X are all the nodes with X zeros in their binary representation.

Then, starting from the bottom layer, connect each item to a random parent at the layer above, until you get a single-component graph.

Note that this graph is a tree, i.e., each node except for the root has exactly one parent.

Then, traverse the tree (starting from the root) and count the total number of paths in it.

UPDATE:

The method above is bad, because you cannot just pick a random parent for a given item - you have a limited number of items from which you can pick a "legal" parent... But I'm leaving this method here for other people to give their opinion (perhaps it is not "that bad").

In any case, why don't you take your graph, extract a spanning-tree (you can use Prim algorithm or Kruskal algorithm for finding a minimal-spanning-tree), and then count the number of paths in it?

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.