Given a graph G, I need to find the number of ways to color it using two colors Black and White.

  1. G will already have some nodes colored Black.
  2. Every node of color White needs to have one or more Neighbors of color Black.

The nodes that are colored Black will always be leaf nodes.



If you only care about graphs with at most $32$ vertices then just list all possible colorings. They are only a constant number ($2^{32}$). For each of them you can decide in constant time whether it is valid according to your constraints.

If you care about graphs with any number of vertices, then the problem is a generalization of the problem of counting the number of dominating sets in a graph, which is #P-complete even for special classes of graphs.

  • $\begingroup$ That value is around 10^9. It'll take a lot of time to run. I need a faster solution. $\endgroup$ – asds_asds Jul 12 '20 at 16:35
  • $\begingroup$ It takes constant time to run. $\endgroup$ – Steven Jul 12 '20 at 16:36
  • $\begingroup$ I don't understand how it takes a constant time? It is exponential wrt the number of vertices. $\endgroup$ – asds_asds Jul 12 '20 at 16:37
  • $\begingroup$ Since the graph has $O(1)$ vertices, there are only $O(1)$ possible colorings (think of each coloring as a boolean vector where each entry corresponds to a vertex). Each coloring can be tested in time proportional to the number of edges of the graph to determine if it satisfies your conditions. The number of edges is again in $O(1)$. The overall time required is therefore constant. $\endgroup$ – Steven Jul 12 '20 at 16:41
  • $\begingroup$ 2^32 * O(1) operations is too large, I need to do it faster. Is it possible to perform this task any faster? $\endgroup$ – asds_asds Jul 12 '20 at 16:43

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.