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.
