-dub-otrezkov-'s blog

By -dub-otrezkov-, 4 weeks ago, translation, In English

As you know, a group of programmers cannot stop talking about problems for more than $$$2$$$ hours, so today at the HSSE Night League, we tried to solve the following problem:

It is necessary to count how many different graphs exist that satisfy the following conditions modulo $$$998244353$$$:

  • The graph has $$$n \le 2000$$$ vertices

  • The graph is connected

  • All edges are distinct and connect different vertices

  • There is exactly one vertex in the graph that is connected to all other vertices (hereinafter referred to as the special vertex)

The solution is not the most obvious and did not come to me immediately. I was able to solve this problem in $$$O(\frac{n^3}{4})$$$, using which you can precompute the answers for each $$$n$$$. This is probably not the most optimal solution, so I would be glad if someone in the comments suggests a faster solution.

So, the solution. First, we remove our special vertex. Now we need to count how many graphs of $$$n-1$$$ vertices exist where there are no vertices connected to all others, and then multiply this value by $$$n$$$ — this will be the desired quantity. We multiply by $$$n$$$ because the "special" vertex could have been any of the $$$n$$$ original vertices.

We will solve the problem using dynamic programming. We will need $$$2$$$ dimensions: $$$dp[i][j]$$$ — the number of graphs with $$$i$$$ vertices and $$$j$$$ special vertices.

Base case:

$$$dp[0][0] = 1$$$. There is only one empty graph.

Transitions:

Let’s assume we have calculated all $$$dp[i-1]$$$. Recalculating $$$dp[i]$$$ using $$$dp[i-1]$$$ is the same as adding a vertex to a graph with $$$i-1$$$ vertices and connecting edges to the new vertex.

Next, consider $$$3$$$ cases:

The number of special vertices has increased, which means we connected the new vertex to all added vertices. The first transition is $$$dp[i][j] \mathrel{+}= dp[i-1][j-1]$$$ for all $$$1 \le j \le n-1$$$.

The number of special vertices remained the same. This means the new vertex is connected to all "special" vertices and to some of the others (but not all, so the number of ways to do this is $$$2^{i - 1 - j}-1$$$). Hence the transition is $$$dp[i][j] \mathrel{+}= dp[i-1][j] \times (2^{i - 1 - j}-1)$$$.

The number of special vertices decreased. Suppose there were $$$k$$$ of them, $$$k > j$$$. It turns out that we connected the new vertex to some $$$j$$$ of those $$$k$$$ (there are $$$\binom{k}{j}$$$ ways to do this), and to some of the others ($$$2^{i - 1 - j}$$$ ways to do this). We get the last transition $$$dp[i][j] \mathrel{+}= dp[i-1][k] \times 2^{i - 1 - k} \times \binom{k}{j}$$$.

$$$\newline$$$

Code
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

As long as there is a special vertex, the graph must be connected, so we can just ignore the connectedness condition.

Let $$$f(n)$$$ be the number of graphs with no special vertex, and then the number of graphs with one special vertex is just $$$nf(n-1)$$$.

Finally, we can use the inclusion-exclusion principle to compute $$$f(n)$$$:

$$$ f(n) = \sum_k (-1)^k \binom n k 2^{\binom {n-k} 2}. $$$
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    A006129 points out that $$$f(n)$$$ is also the number of edge covers of $$$K_n$$$. It is a cute exercise to see why this is the case.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Wow this is extremely beautiful formula, but can you please explain why it works?

    UPD: I understood why it works. Impressive