I was working on problem 1221G - Graph And Numbers, which required calculating the amount of independent sets on a graph of at most $$$40$$$ nodes. I came up with a heuristic algorithm, which I know is exponential, but I also know it's pretty good in practice, which explains the AC 65276338. First some definitions:
My solution is reduced to the following function:
This approach is correct, because the amount of independent sets for a graph split on several components, it is sufficient to multiply the answers of each component. For a connected graph, there are two possible cases: $$$x$$$ is not included in the set ($$$x$$$ is the node with greatest cardinality) or $$$x$$$ is included the set. For the first case, delete $$$x$$$ and all its edges from the graph and solve recursively. For the second case, all nodes adjacent to $$$x$$$ must not be included in the set, so delete $$$x$$$ and all of its adjacent nodes, and solve recursively.
This is a backtracking solution. It's fast because it always deletes as much edges as possible when the graph is connected, making the graph become either empty or disconnected very fast. Whereas when it's disconnected, it solves each component independently, and then multiplies the results, instead of recursively solving all possibilities.
Even though I know this solution does well in practice, I'm still very curious for its actual time complexity. Here's where I need help, I don't even know how to find the worst-case scenario. Any ideas?