2
$\begingroup$

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.
$\endgroup$
  • 2
    $\begingroup$ Sooo... this is the question in the exam. What did you try to solve it? $\endgroup$ – Did Feb 5 at 14:51
  • $\begingroup$ 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 $\endgroup$ – Aqua Feb 5 at 15:16
  • $\begingroup$ Hmm, are you sure? Perhaps you should swich u and v in that formula? $\endgroup$ – Aqua Feb 5 at 15:33
3
$\begingroup$

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$]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.