1
$\begingroup$

enter image description here

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.

$\endgroup$
4
  • $\begingroup$ I don't understand the problem statement. What is the input to the algorithm? What is meant by "(up,down,left,right) description of each vertex"? What do you want the algorithm to output? You say "recreate the spanning tree", but which spanning tree do you want and how is it related to the input? You say "satisfy the connected properties" but you don't define what you mean by that; please specify clearly what properties you have in mind. Can you share the motivation for this task or the context where you encountered it? $\endgroup$
    – D.W.
    May 31, 2022 at 2:07
  • $\begingroup$ @D.W. I have added a fully worked out example. $\endgroup$
    – Looft
    May 31, 2022 at 7:10
  • $\begingroup$ Is the grid graph known and given as input? In particular, is the number of rows and columns known / given as input? $\endgroup$
    – D.W.
    May 31, 2022 at 19:14
  • $\begingroup$ Yes, grid dimensions are known. $\endgroup$
    – Looft
    May 31, 2022 at 21:21

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Interesting perspective, I guess the fact that there's so many spanning trees I should be able to devise an algorithm that will stumble upon any spanning tree that decodes to the description array. $\endgroup$
    – Looft
    May 31, 2022 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.