# Data-structure for functions of independent sets

Suppose I have a graph $G$, with nodes $\{1,2,\ldots,n\}$, subsets of nodes $\{b_1,\ldots,b_k\}$ and functions $\{f_1,\ldots,f_k\}$ where $f_i$ maps independent subsets of $b_i$ to reals. The operation on $f$ is setting or getting all values in "canonical order", ie, $\langle f(\emptyset),f(\{1\}),f(\{2\}),f(\{3\}),f(\{1,2\}),\ldots \rangle$.

What is a way to do this more efficiently than with an array of size $2^{|b_i|}$ for $f_i$? This comes up when counting independent sets on graphs

• I don't see how this could be any easier than that. What if the graph has no edges? Isn't the problem still impossible to solve more efficiently? Commented Jan 3, 2011 at 22:18
• I'm looking for a way to take structure of G into account. For instance, if G is fully connected, that array representation is not efficient because each function would have $k$ values but array will have $2^k$ entries. In actual application, graph G and $b_i$'s would be given Commented Jan 3, 2011 at 22:56

I wanted to post a comment, but with no "karma" it seems impossible... What about using dictionaries (hashmap, depending on the language you use) to store the values of your $f_i$ ? This way you don't have to know beforehand the size of the memory you will need, and gettin a function's value is not too slow.