P5492 [PKUWC2018] Randomized Algorithm

We know that finding the maximum independent set of an arbitrary graph is an NP-complete problem. Currently, there is no exact polynomial-time algorithm, but there are many polynomial-time approximation algorithms. For example, one algorithm often used by Little C is: 1. For an undirected graph with $n$ vertices, first uniformly randomly generate a permutation $p[1\ldots n]$ of $1\ldots n$. 2. Maintain an answer set $S$. Initially, $S$ is empty. Then, in the order $i=1\ldots n$, check whether $\{p[i]\}\cup S$ is an independent set. If it is, set $S=\{p[i]\}\cup S$. 3. Finally, obtain an independent set $S$ as the answer. Now Little C wants to know, for a given graph, the probability that this algorithm is correct. Output the answer modulo $998244353$.

The first line contains two non-negative integers $n,m$, representing the number of vertices and edges of the given graph. The next $m$ lines each contain two positive integers $(u,v)$ $(u\neq v)$, describing an undirected edge of the graph.

Output the probability of being correct, modulo $998244353$.

#### Sample Explanation The maximum independent set size of this graph is clearly $2$. It can be seen that only when $p[1]=2$ will we get $S=\{2\}$; otherwise, we always get $S=\{1,3\}$. Therefore, the answer is $\frac{2}{3}$. #### Constraints For $10\%$ of the testdata, $1\leq n\leq 9$. For $30\%$ of the testdata, $1\leq n\leq 13$. For $50\%$ of the testdata, $1\leq n\leq 17$. Another $10\%$ of the testdata satisfies that the given graph is a path. Another $10\%$ of the testdata satisfies that the given graph is a tree. For $100\%$ of the testdata, $1\leq n\leq 20$, $0\leq m\leq \frac{n\times (n-1)}{2}$. It is guaranteed that the given graph has no multiple edges and no self-loops. Translated by ChatGPT 5