Spanning tree on grid with minimum number of turns

Question

Is there a polynomial algorithm to find a spanning tree of an undirected grid graph which minimizes the number of turns in tree? A turn is when there are two edges connected to one vertex which have perpendicular directions.

In this problem we have arbitrary set of cells in grid which form a connected graph (not only rectangles are considered).

For example, given a 4 x 4 grid graph (see image below), we want to find a spanning tree like that on the right (which has 6 turns) rather than that on the left (which has 14):

Ideas about approximate algorithms may be useful too.

My idea we should start with building any tree and then trying to improve the tree by connecting vertexes the other way (using en.wikipedia.org/wiki/Breadth-first_search) until we can't impove the result — Sergey Prosin
I would assume that the graph with minimum number of turns always consists of one side of your grid (N, E, S, W) and perpendicular arms. Basically, a generalization of your right spanning tree. Use the side with the lowest number of turns as base side. As long as the initial grid is "convex" (under Manhattan Distance) this should work. — SaiBot
For rectangles it is true that spanning tree with minimum number of turns consists of one leng side of grid and perpendicular arms. But, not only rectangular grids are considered. For example, T-shaped and H-shaped grids are considered too. Or grids with holes (some cells missing) — Alex Row
As I said this should work as long as the grid is convex. Should also work for the T and H example (although H is not convex) — SaiBot

David Eisenstat David Eisenstat · Accepted Answer · 2018-08-03T13:01:51

I would try integer programming (translate the constraints and objective below to a format accepted by a solver like GLPK and let GLPK figure out the optimal solution).

For each vertex v of the graph, there are up to 15 0-1 variables

         x(v, ╵), x(v, ╶), x(v, └),

x(v, ╷), x(v, │), x(v, ┌), x(v, ├),

x(v, ╴), x(v, ┘), x(v, ─), x(v, ┴),

x(v, ┐), x(v, ┤), x(v, ┬), x(v, ┼),

where each variable is 1 if it describes the connections of v in the spanning tree and zero otherwise. For each edge vw, we have a 0-1 variable y(vw) that is 1 if the edge is present.

The objective is to minimize

sum_{vertices v} (  x(v, └) +   x(v, ┌) +   x(v, ┘) +   x(v, ┐) +
                  2 x(v, ├) + 2 x(v, ┴) + 2 x(v, ┤) + 2 x(v, ┬) +
                  4 x(v, ┼)).

For each vertex v, we have a constraint

sum_{connections c} x(v, c) = 1,

because there is exactly one set of connections. For each edge vw, we have constraints

sum_{connections c around v with vw} x(v, c) = y(vw),
sum_{connections c around w with vw} x(w, c) = y(vw),

encoding the correspondence between the two sets of variables.

The difficult constraint is the connectivity constraint. In theory, we write this as

for every subset S of vertices,
    sum_{edges vw such that v in S and w not in S} y(vw) >= 1,

i.e., every cut has at least one edge crossing it, but in practice there are exponentially many of these, which is not good. I can think of three ways around this problem. From easiest to hardest,

Starting with just the constraints above, solve the instance to optimality. Check whether the solution is connected with depth-first search. If not, add the corresponding constraint (e.g., S is the set of visited vertices), and resolve.
Formulate the connectivity constraint by adding variable that express the existence of n - 1 capacity-respecting unit flows between the endpoints of each edge of an arbitrary spanning tree of vertices. I can elaborate if you want to try this.
Like Solution 1, but we find the cut inside the solver for the linear programming relaxation. This requires an implementation of max flow (since the edge variables can have any floating point value between 0 and 1) to find capacity of the min cut as well as hooks into the IP solver.

We don't need a no-cycles constraint. If a solution contains a cycle, then we can always eliminate a corner by deleting a cycle edge, so the optimal solution has no cycle.

Spanning tree on grid with minimum number of turns

1 Answers