# Past exam question: probabilistic method

Let $$G=(V,E)$$. We want to give for each vertex $$v$$ in $$V$$ a number $$f_v$$ s.t. for every vertex we have $$(\sum_{v: (u,v)\in E} f_v)+f_u \not \equiv 0 \mod{(n+1)}$$

Let A be the following algorithm to solve the problem:

For each vertex, select a random number between $$0$$ and $$n$$ see if it is a good solution. If so, return the solution, otherwise - return to the beginning of the algorithm.

1. Prove that if there is a solution, the running time of the algorithm is polynomial. What's the expectation?
2. Use the probabilistic method to prove that there is always a solution to the problem.
• Sooo... this is the question in the exam. What did you try to solve it? – Did Feb 5 at 14:51
• What does this means :$$\sum_{u: (u,v)\in E} f_v+f_u?$$ Is it $$( \sum_{u: (u,v)\in E} f_v)+f_u$$ or $$\sum_{u: (u,v)\in E} (f_v+f_u) ?$$ or something else – Aqua Feb 5 at 15:16
• Hmm, are you sure? Perhaps you should swich u and v in that formula? – Aqua Feb 5 at 15:33

## 1 Answer

HINT: The function

$$g(v) \doteq f_v + \sum_{u: uv \in e(G)} f_u \mod (n+1)$$

is uniformly distributed amongst $$\{0,1,\ldots, n \}$$ so for any graph $$G$$ on $$n$$ vertices the following holds: For each vertex $$v \in G$$, the probability that $$g(v)$$ is 0 is $$\frac{1}{n+1}$$. Thus by the union bound the probability that this algorithm fails to find a good solution (for any graph $$G$$) is at most $$n \times \frac{1}{n+1} = \frac{n}{n+1} = 1 -\frac{1}{n+1} >0$$. So for any $$G$$, there is indeed a positive probability that this algorithm will find a solution, which of course implies that there indeed is a solution to be found in the first place.

Furthermore, from the above paragraph the probability that this algorithm fails to find a good solution after $$\ell$$ iterations is at most $$\left(\frac{n}{n+1} \right)^{\ell}$$. Thus the expected running time of this algorithm is at most $$\sum_{\ell=1}^{\infty} \ell \left(\frac{n}{n+1} \right)^{\ell}$$. I leave it to you to show that this is polynomial in $$n$$.

Now if $$g(v)$$ were (say) $$\sum_{uv \in E(G)} (f_u + f_v)$$ then it would not necessarily hold that $$g(v)$$ is uniformly distributed amongst $$\{0,1,\ldots, n\}$$. If e.g., $$G$$ were a multigraph and each edge appeared twice and $$n+1$$ were even then $$g(v)$$ would be even as well. [If $$n+1$$ is even then the parity of $$m$$ $$\mod (n+1)$$ is well-defined for all integers $$m$$]