eidan's blog

Efficiency on heuristic solution
By eidan, history, 5 years ago, In English

I was working on problem 1221G - Граф и числа, 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?

  • Vote: I like it
  • +41
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since there are multiple ways to implement this recursion (like computing $$$M(G)$$$ efficiently), I'll instead give an upperbound to the number of recursion calls, let it be $$$T(n)$$$ where $$$n = |G|$$$, and $$$G$$$ is connected.

So, if $$$n = 2$$$ then both nodes have degree 1, this case has O(1) calls. Otherwise, there exists a node with degree at least 2, which you will remove, so an upperbound is: $$$T(n) = 2 + T(n - 1) + T(n - 3)$$$. Even though you can run dp to compute this, it is known $$$T(n) = c^n$$$ (well actually a polynomial, but let's only look at the largest exponent) for some constant $$$c$$$.

So, $$$c^4 = 2 + c^3 + c$$$, which appears to be about $$$1.73^n$$$. Of course we didn't consider whenever a component splits and such (and also some degrees will be more than 3).

Also, if $$$M(G) = 2$$$ then the graph is either a line of a circle. You can precompute with dp the answer for such a graph, and now the recursion finds a degree at least 3. With the same process, the result is about $$$1.58^n$$$.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Isn't it $$$c^4=c^3+c$$$ and $$$c \approx 1.47$$$?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yeah, pretty sure you don't consider constants like he did.

      And when the degree is at least $$$3$$$, you get $$$1.38^n$$$.

      → Reply