Number of trees that can be formed by deleting nodes in a graph

Question

0
|
0__1__0
|  |  |
1__1__0
   |
   1

Let's say I have a undirected graph. We have these conditions:

1. You are only allowed to delete nodes labeled as '1'.

2. Deletion of any node must not make the graph a forest

We are allowed to delete multiple nodes, but the above conditions must be satisfied.

Count the number of different trees(unrooted) that can be made by the above process. Note that there is no such thing as 'root' here. We only count the different structures.

For the above, answer is 4 because:

0
|
0     0
|     |
1__1__0        ------> #1
   |
   1

0
|
0     0
|     |        -------> #2
1__1__0


0
|
0__1__0
|     |       ---------> #3
1     0

0
|
0__1__0       ---------> #4
      |
      0

I would appreciate any kind of help or hints.

(In case the graph is already a tree, we are still allowed to delete nodes to get new trees, subject to the above conditions)

Answer 1

As you have already pointed out, a naive exponential solution would be to take all subsets of the 1-nodes and for each, checking that removing the nodes gains a tree graph. Two thoughts how you could prune some of the subsets:

1. Build the 1-node subsets incrementally from the smallest to the largest. If you find one that partitions the graph, you don't need to check any of its supersets.

Let me denote the 1-nodes in your example A, B, C, D:

0
|
0__A__0
|  |  |
C__B__0
   |
   D

Removing {A, B} partitions the graph. Therefore obviously removing {A, B, C} or {A, B, D} or{A, B, C, D} also partitions the graph. You don't need to explicitly check any of those.

(Unless all but one of the partitioned graph components consist solely of the 1-nodes. Then removing all these 1-node components could also gain a valid solution. You may need to check this as a special case.)

2. Once you find a 1-node subset that gains a tree; then removing any further 1-node will also gain a tree as long as the graph is not partitioned.

For example, by removing A we get a tree:

0
|
0     0
|     |
C__B__0
   |
   D

We can generate additional trees by removing further nodes. For these we only need to check that by removing them we don't partition the graph. If not, we can be sure the graph remains a tree. Removing D in this example illustrates the idea.

These optimizations probably won't make the algorithm better than exponential in the worst case, but they could make it practical for reasonably small input.