Efficiency on heuristic solution

Revision en1, by eidan, 2019-11-18 08:34:25

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:

$$$\\M(G)\text{ yields the node with largest cardinality in graph }G$$$
$$$\text{For a graph }G\text{ and a node }x \in G\text{, }A(x, G) = \{x\}\cup\{y\text{ }|\text{ }y \in G, y\text{ is adjacent to }x\}$$$
$$$H(G) \text{ for a disconnected graph }G\text{ yields the set of connected components that conform }G$$$
$$$\text{For a graph }G\text{ and a subset of nodes }S \subseteq G, $$$
$$$G - S\text{ denotes the deletion of all nodes in }S\text{ from }G\text{, and all edges incident to at least one node in }S$$$

My solution is reduced to the following function:

$$$F(G) = \begin{cases} 1 & \text{if }G\text{ is an empty graph} \\ F(G) = \prod\limits_{h \in H(G)}{F(h)}& \text{if }G\text{ is not connected} \\ F(G) = F(G - \{x\}) + F(G - A(x, G))\text{, where } x=M(G) &\text{otherwise}.\end{cases} $$$

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English eidan 2019-11-18 08:34:25 2315 Initial revision (published)