<p>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.</p>

CC BY-SA 2.5
2011-01-04T16:41:20.817Z
Hm...I think you are right, I was overthinking it
Yaroslav Bulatov
CC BY-SA 2.5
2011-01-04T09:17:36.043Z
2011-01-04T09:17:36.043Z
Nathann Cohen
<p>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$.</p>

<p>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</p>

CC BY-SA 2.5
2011-01-03T22:18:21.030Z
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
CC BY-SA 2.5
2011-01-03T22:56:17.867Z
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
<ds.algorithms><ds.data-structures>
Data-structure for functions of independent sets
Yaroslav Bulatov
# Data-structure for functions of independent sets

(Asked by: username_0 on 2011-01-03)

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

**Tags:** ds.algorithms, ds.data-structures

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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  

---

## 1 answers

### Answer by username_2 on 2011-01-04. Score: 1 | Accepted 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.

> **Comments:**
> **username_0**: Hm...I think you are right, I was overthinking it  

---

