4
$\begingroup$

There's the classical problem of sorting numbers in a list with the restriction that you can only swap two neighbouring numbers. It's easy to see that getting an optimal number of needed swaps can be achieved by insertion sort or bubble sort.

We can generalize this problem by changing the underlying structure from a list to a graph. Instead of swapping neighbouring numbers in a list we would be swapping numbers connected by an edge. Formally let's have a graph G=(V, E) with V = {1, ..., N} and an assignment of values f: V -> {1, ..., N} where f is a bijection/permutation. In order to do a swap we select an edge {u, v} from E and switch f(u) with f(v). Our goal is to sort f (that is achieve a state when f is the identity) in the least number of swaps. My question is whether there is a (polynomial) algorithm for this.

Since working on general graphs seems really difficult from what I've tried let's restrict ourselves to G being a tree. This should be a simpler question because each number has a clear path to its target.

Some observations:

When G is a path graph the problem is the same as sorting a list which is simple.

When G is a complete graph the problem is also simple since we only need to decompose each cycle into transpositions. You can actually look at the general problem as decomposing a permutation into as few transpositions as possible with the restriction of which transpositions you are allowed to use.

As long as the graph is connected there's a lower bound of "sum of all distances to targets"/2 because each swap decreases the distance to target of at most two numbers. The upper bound is "sum of all distances to targets" because we can select a number that wants to be in a non-articulation vertex (or simply leaf in trees) and drag it there. Then we can forget about this vertex and reduce the problem to a smaller graph.

$\endgroup$
  • $\begingroup$ Basically you want to swap the minimum number of edges to go from one graph to another, is that right? $\endgroup$ – klaus Oct 27 '17 at 14:02
  • $\begingroup$ Yes, that's another way to look at it - you have two isomorphic graphs with different labeling by the set {1, ..., n} and you want to find the shortest sequence of swaps to get from one graph to the other. (By swapping here I mean swapping labels on the vertices of an edge.) $\endgroup$ – Pavel Madaj Oct 27 '17 at 14:08
2
$\begingroup$

This problem is called Token Swapping, and you can find more information if you search by its name on google.

I couldn't find a proof that it is NP-complete on trees, but I've found a recent paper that gives a 2-approximation algorithm for trees: http://erikdemaine.org/papers/TokenReconfiguration_FUN2014/paper.pdf

$\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.