# 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? – Andrew D. King Jan 3 '11 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 – Yaroslav Bulatov Jan 3 '11 at 22:56

## 1 Answer

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.

• Hm...I think you are right, I was overthinking it – Yaroslav Bulatov Jan 4 '11 at 16:41