10
$\begingroup$

Let $G= (V, E)$ be a non-regular connected graph whose degree is bounded. Suppose that each node contain a unique token.

I want to uniformly shuffle the tokens amongst the graph using only local swaps (i.e. exchange of the tokens between two adjacent nodes) ? Is there a lower bound known for this problem ?

The only idea I had is to use a random walk result, then to see how much swaps I need to "simulate" the effect of random walks transporting tokens on the graph.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What kind of lower bound you are looking for? Total number of swaps? Number of parallel rounds (i.e., in 1 step you can swap along all edges of a matching in $G$)? Lower bound as a function of $|V|$, $diam(G)$? Do all the nodes know the topology of $G$ (and can adapt their behaviour accordingly), or are you looking for a fixed strategy that you can apply in any graph? $\endgroup$
    – Jukka Suomela
    Aug 18, 2010 at 11:39
  • 2
    $\begingroup$ I should have been more specific, sorry. The goal is to design a data dissemination method for sensor networks that avoid problems of random walks based methods (essentially loss of information due to several tokens colliding at the same node). So I am interested in the total number of swaps (this will give the number of messages circulating in the network) and the number of rounds (to have a rough estimate of the convergence time). a LB as a function of $V$ is fine and nodes are not topology aware (unfortunately). $\endgroup$
    – Sylvain Peyronnet
    Aug 18, 2010 at 12:54

2 Answers 2

Reset to default
5
$\begingroup$

Suppose your graph was a path. I think then this problem becomes equivalent to sorting a random sequence of numbers in an array by swapping adjacent entries. Even of all nodes are topology aware, you get a n^2 lower bound on the number of swaps (cannot do better than bubble sort which is n^2 even on a random input).

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ In the case of a path, the process of swapping with probability 1/2 mixes in $O(n^2)$, this has been proven by Benjamini, Berger and Hoffman (this was conjectured by Diaconis and Ram). So my LB is also a function of the degree I guess... $\endgroup$
    – Sylvain Peyronnet
    Aug 18, 2010 at 17:27
  • $\begingroup$ This LB says you can't improve the algorithm even if you can choose your swaps.... but right, I guess the problem might get easier as the (average?) degree goes up. $\endgroup$
    – Lev Reyzin ♦
    Aug 18, 2010 at 17:37
  • $\begingroup$ I will schedule some simulations to see how thing goes when the degree is growing. $\endgroup$
    – Sylvain Peyronnet
    Aug 18, 2010 at 17:38
  • 1
    $\begingroup$ Actually it looks like this LB (with some modification) will hold even if the two ends of the path have large cliques -- as in 2 cliques on n/4 connected by a path of n/2 nodes. Now the average degree is O(n), yet you still can't beat n^2. Perhaps we need to impose a minimum degree? $\endgroup$
    – Lev Reyzin ♦
    Aug 18, 2010 at 17:39
  • $\begingroup$ Yes, we need a minimum degree :( $\endgroup$
    – Sylvain Peyronnet
    Aug 19, 2010 at 9:20
5
$\begingroup$

I'd like to point out the relation between this problem and sorting networks. For example, if your graph is a path, then the trivial linear-depth sorting network also shows that you can obtain any permutation in linear number of rounds. Moreover, this is tight, as simply interchanging the elements at the endpoints of the path requires a linear number of rounds.

AKS sorting networks show that there are graphs in which you can obtain any permutation in logarithmic number of rounds. For the case of grid graphs, see e.g. these lecture notes.

(Of course sorting and shuffling are different problems, but many upper and lower bounds are related. E.g., pick random labels and sort by labels.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the pointer. I will dig in this direction, maybe it is not what I need here (I am not sure whether I have the good type of graph) but it certainly will be something I will use sooner or later ! $\endgroup$
    – Sylvain Peyronnet
    Aug 18, 2010 at 20:26

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.