Recreate a spanning tree in a grid graph given vertex descriptions

Question

Let's assume I have graph above with spanning tree pointed out by blue edges.

Vertex at position (1,1) (row 1, column 1) is connected to the bottom vertex and has degree 1.

Vertex at position (4,2) (row 4, column 2) is connected to the up, left and right vertex and has degree 3.

Let's call (up, down, left, right) a description of a vertex. For a vertex that is connected to a vertex above it and a vertex left to it, description is (1, 0, 1, 0). For a vertex that is connected to a vertex above, below, left and right to it, description is (1, 1, 1, 1).

Given an array of descriptions of vertices that belong to a spanning tree of a grid graph, dimensions of the grid, recreate a spanning tree that decodes to a given array of descriptions.

For example, for the image above an input to the algorithm could be:

[
  (0, 0, 1, 0),  # this one describes vertex at position (4, 4), it is connected to the vertex on the left
  (1, 0, 1, 1),  # vertex (4, 2)
  (0, 1, 1, 0),  # vertex (2, 4)
  (1, 0, 1, 1),  # vertex (2, 3)
  (1, 0, 1, 1),  # vertex (2, 2)
  (1, 0, 0, 1),  # vertex (2, 1)
  (0, 1, 0, 0),  # vertex (1, 2)
  (0, 1, 0, 0),  # vertex (3, 1)
  (0, 1, 0, 1),  # vertex (1, 3)
  (1, 0, 1, 0),  # vertex (3, 4)
  (0, 1, 0, 0),  # vertex (1, 1)
  (0, 1, 0, 1),  # vertex (3, 2)
  (0, 0, 1, 0),  # vertex (1, 4)
  (0, 0, 1, 1),  # vertex (4, 3)
  (0, 0, 1, 1),  # vertex (3, 3)
  (1, 0, 0, 1),  # vertex (4, 1)
]

One of the possible outputs can be (reordered array of descriptions, but I can go over each description and color the edges in an empty grid and get the image above):

[
  (0, 1, 0, 0),  # vertex (1, 1)
  (0, 1, 0, 0),  # vertex (1, 2)
  (0, 1, 0, 1),  # vertex (1, 3)
  (0, 0, 1, 0),  # vertex (1, 4)
  (1, 0, 0, 1),  # vertex (2, 1)
  (1, 0, 1, 1),  # vertex (2, 2)
  (1, 0, 1, 1),  # vertex (2, 3)
  (0, 1, 1, 0),  # vertex (2, 4)
  (0, 1, 0, 0),  # vertex (3, 1)
  (0, 1, 0, 1),  # vertex (3, 2)
  (0, 0, 1, 1),  # vertex (3, 3)
  (1, 0, 1, 0),  # vertex (3, 4)
  (1, 0, 0, 1),  # vertex (4, 1)
  (1, 0, 1, 1),  # vertex (4, 2)
  (0, 0, 1, 1),  # vertex (4, 3)
  (0, 0, 1, 0),  # vertex (4, 4)
]

The array can come in any order (there is no way to know for which position the description is). Of course, vertices in the first row can never be connected to a vertex above (there is no row above), similarly, vertices in the last row, first column, last column, cannot be connected to vertices below, left, or right, respectively.

Is there an efficient algorithm that will recreate the spanning tree or enumerate all possible spanning trees that decode to the given descriptions array.

I think that from the given array there are multiple spanning trees of a grid graph (the array does not uniquely define the spanning tree shown on the picture). Similarly, if I was given a sorted degree array [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] (decoded from the image above), I could construct a variety of trees that satisfy this degree array but some of these trees would not span a grid.

Problem is related to the game described here https://math.stackexchange.com/questions/3191645/uniqueness-of-spanning-tree-on-a-grid/3191756 but there one can rotate things, here, we just have shuffled grid and need to recreate some spanning tree of the grid by repositioning the elements.

Answer 1

It's not possible. There isn't enough information in the input, even if you had unlimited computing time.

The order of the input is irrelevant. So, we could equivalently specify the input as follows. Each node can be assigned to one of 16 different descriptions (for instance, a node that is connected to one above it and one to the left of it has description (1,0,1,0)). So, the input could equivalently be described by providing 16 counts: for each description, a count of how many nodes have that description.

And now we can see that, for large grid graphs, the number of possible spanning trees exceeds the number of possible inputs. So, you can't hope to uniquely recover the spanning tree from just this information. Moreover, there can be exponentially many spanning trees that are consistent with any one given input, so there is also no efficient algorithm to enumerate all possible spanning trees that match the input.

Why? Suppose you have a $m\times n$ grid graph, where $m>2$ and $n>2$. Then the number of spanning trees of this grid graph is exponential in $mn$. However, the number of possible inputs is at most $(nm+1)^{16}$, since there are 16 descriptions and for each description we have a count that ranges from $0$ to $nm$. The latter number is polynomial in $nm$, so when $nm$ is large, we find that the number of possible spanning trees vastly exceeds the number of possible inputs.