1

I'm thinking that there are two cases for each sub-tree: the root is in the independent set and the root is not in the set. How to write a recursive algorithm for finding the number of independent sets in a tree? The tree is n-ary.

https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

This is my solution so far, but it isn't correct. The variable parentIncluded is equal to true if the parent of the current subtree is already included in the independent set, thus the root of the current subtree can't be added to the independent set. If parentIncluded is equal to false, then the root of the current subtree can be added to the independent set. There are two cases for when parentIncluded is false. The first case: Add the root to the set. Second case: don't add the root.

public static int numberOfIndependentSets(Binary root) {
        if (root == null) {
            return 1;
        }
        return numberOfIndependentSets(root, false) + 1;
    }

    private static int numberOfIndependentSets(Binary current, boolean parentIncluded) {
        if (current.left == null && current.right == null) {
            if (parentIncluded) {
                return 0;
            } else {
                return 1;
            }
        }
        int total = 0;
        if (parentIncluded) {
            int left = numberOfIndependentSets(current.left, false);
            int right = numberOfIndependentSets(current.right, false);
           total += (left + 1) * (right + 1) - 1;
        } else {
            // include current node
            int left = numberOfIndependentSets(current.left, true);
            int right = numberOfIndependentSets(current.right, true);
            total = (left+1) *( right +1);

            // not include current node
            left = numberOfIndependentSets(current.left, false);
            right = numberOfIndependentSets(current.right, false);
            total += (left+1) * (right+1) -1;
        }
        return total;
    }
jas7
  • 2,893
  • 6
  • 23
  • 36
  • @GordonLinoff See this Wiki page for the definition of independent set. https://en.wikipedia.org/wiki/Independent_set_(graph_theory) – jas7 Jan 28 '17 at 14:52
  • There's more than 2 cases for each sub-tree. E.g. consider a tree that is a list: `a->b->c->d`, with `a` as root. There are two independent sets which contain `a`: `{a, c}` and `{a, d}`. –  Jan 28 '17 at 14:55
  • In pure graph theory, trees don't have roots. They are just acyclc connected graphs. Since specifying a node as the root isn't going to change the answer, i'd be surprised if the root (supposing that one exists) will play a role. – John Coleman Jan 28 '17 at 14:56
  • 1
    Are you talking about maximal independent sets? Otherwise make each node a singleton set. – Henry Jan 28 '17 at 14:58
  • @JohnColeman I agree with you that specifying a node as the root won't alter the answer. The input is a tree, but any node could be the root. – jas7 Jan 28 '17 at 14:58
  • Do you want to really count the number of independent sets or you just want to find a maximum independent set. Also are you looking for random independent sets or just maximum or maximal? a single vertex is already an independent set – Saeed Amiri Jan 28 '17 at 14:58
  • @Henry. No, I'm not talking about maximal independent sets. – jas7 Jan 28 '17 at 14:59
  • @SaeedAmiri I want to count the number of independent sets. The independent set could be maximal or not. Yes, a single vertex is an independent set. An empty set is also an independent set. I need an algorithm for finding the number of independent sets. – jas7 Jan 28 '17 at 15:00
  • I would focus on a leaf node, chosen at random. Either it is in the independent set or it isn't. If it is in the independent set, then you need to exclude its unique neighbor. If it isn't -- then there is no restriction on which nodes can be chosen from the rest of the graph. This should be enough to get a recursive function to count them. – John Coleman Jan 28 '17 at 15:01
  • @JohnColeman . . . That is a reasonable approach because the leafs are all equivalent (from the perspective of affecting an independent set). However, you need to consider all subsets of each leaf. – Gordon Linoff Jan 28 '17 at 15:20

1 Answers1

2

Your basic idea should work.

You could defined two mutually recursive functions on the set of rooted trees:

f(T) = number of independent sets containing the root
g(T) = number of independent sets not containing the root

You want to compute f(T) + g(T)

For 1-node trees, L, as basis cases we have:

f(L) = 1
g(L) = 1

Say that T_1, T_2, .. T_n are the subtrees of the root. Then the recursive equations are:

f(T) = g(T_1)*g(T_2)* ... *g(T_n)
g(T) = (f(T_1)+g(T_1))*(f(T_2)+g(T_2)) * ... * (f(T_n)+g(T_n))

As a check: you can use this to get the number of independent sets of full binary trees with n levels (equivalently, height n-1). Make the f, g a function of level. A Python implementation:

def f(n):
    if n == 1:
        return 1
    else:
        return (g(n-1))**2

def g(n):
    if n == 1:
        return 1
    else:
        return (f(n-1) + g(n-1))**2

def h(n): return f(n)+g(n)

[h(n) for n in range(1,7)] evaluates to

2, 5, 41, 2306, 8143397, 94592167328105

This is sequence A076725 in the Online Encyclopedia (slightly shifted) which is described as "the number of independent sets on a complete binary tree with 2^(n-1)-1 nodes", so it seems that this approach makes sense.

John Coleman
  • 51,337
  • 7
  • 54
  • 119