1
$\begingroup$

Suppose we have a graph $G(V,E,W)$, where $V$ and $E$ are the set of vertices and edges and $W$ is non-negative weight on the edges. Let $w(e)$ be the weight of edge $e$ and $N(e)$ be the neighboring edges of $e$. An edge $e$ is locally subdominant if its weight is smaller than all of its neighbors. With this background Let we have the following algorithm,

for e in E 
if w(e) is locally sub-dominant 
    delete e from the graph G
    double weights of all e in  N(e) 

My question is after this loop ends what can we say about uniform randomness of the remaining edges. Are they still uniform random?

$\endgroup$
  • $\begingroup$ What do you mean by "uniform randomness"? $\endgroup$ – Yuval Filmus Oct 8 '18 at 16:55
1
$\begingroup$

Let us consider the simplest case, that of a path of length two edges, which are drawn uniformly and independently from $[0,1]$. Let us suppose that the first edge is sub-dominant, which happens with probability 1/2. The probability that the weight of second edge is at most $t \in [0,1]$ is $$ \Pr[x \leq y \leq t \mid x \leq y] = \Pr[x,y \leq t] = t^2. $$ Here $x$ is the weight of the first edge, and $y$ is the weight of the second edge. We see that even before doubling, the distribution of $y$ is non-uniform.

Next, let us examine the case of a star with three edges, again drawn uniformly and independently from $[0,1]$. Again suppose that the first edge is sub-dominant, which happens with probability 1/3. The probability that the weight of the second edge is at most $t \in [0,1]$ while that of the third edge is at most $u \in [0,1]$ is $$ \Pr[y \leq t, z \leq u \mid x \leq y,z] = 3 \int_0^{\min(t,u)} (t-x)(u-x) \, dx = \\ 3tum - \frac{3}{2}(t+u)m^2 + m^3. $$ Here $x,y,z$ are the weights of the first, second, and third edges, respectively, and $m = \min(t,u)$. Substituting $u = 1$, we obtain $$ \Pr[y \leq t \mid x \leq y,z] = \frac{3t^2-t^3}{2}. $$ Calculation shows that for generic $t,u$, $$ \Pr[y \leq t, z \leq u \mid x \leq y,z] \neq \Pr[y \leq t \mid x \leq y,z] \Pr[z \leq u \mid x \leq y,z], $$ that is, the remaining weights are no longer independent.

$\endgroup$
  • $\begingroup$ But what if we create two separate subgraphs as follows. We take the least k weight edges (say F) of G and make a subgraph, G[F] spanning these edges. We run the above algorithm on top of that. Note that when the algorithm runs on G[F] some of the edges not in F can be doubled as these neighboring edges may not be part of F. Now can we argue that the weight of the remaining edges i.e., E-F are uniformly distributed among themselves? $\endgroup$ – user2104150 Oct 11 '18 at 14:00
  • $\begingroup$ Probably doesn’t help. $\endgroup$ – Yuval Filmus Oct 11 '18 at 14:34

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.