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

  • $\begingroup$ 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? $\endgroup$ – Andrew D. King Jan 3 '11 at 22:18
  • $\begingroup$ 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 $\endgroup$ – Yaroslav Bulatov Jan 3 '11 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.

| cite | improve this answer | |
  • $\begingroup$ Hm...I think you are right, I was overthinking it $\endgroup$ – Yaroslav Bulatov Jan 4 '11 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.