7
$\begingroup$

I'm looking to create maps for a board game with some specific properties, but my knowledge of graph theory is essentially negligible so I'd love some help. The maps will consist of territories which border each other in a 2D plane, I'm looking for a method for creating graphs which represent these maps, with vertices representing territories, and edges representing border. The key property of these graphs is;

  • There is only one path of minimum length between any two vertices.

Other properties include:

  • The graph is bidirectional.
  • Each vertex in the graph is accessible from every other vertex.
  • For paths between vertices there is no limit to the number of paths longer than the minimal length.
  • The edges all have the same weight.

From what I understand Dijkstra's algorithm allows me to find the shortest path between two points, but how do I specify that only one such path exists? Any help is much appreciated :)

$\endgroup$
  • $\begingroup$ "There is a maximum number (say 5 for example) of edges between each vertex." What do you mean by this? $\endgroup$ – Lorenzo Najt Jul 10 at 1:30
7
$\begingroup$

A graph with the property that for every pair of nodes, there is a shortest path is sometimes called 'min-unique.' (Usually this concept is used in the directed graph context, where it has complexity theoretic meaning.)

I'll discuss below an algorithm to verify min-uniqueness of weighted undirected graphs, with non-negative weights.

I suspect that the class of undirected unweighted min-unique graphs might be pretty limited. Some observations and a conjecture is in the last section.


If you want to verify that a graph is min-unique:

  • One way to count the number of length $k$ paths between nodes $s$ and $t$ is by taking the $s,t$th entry of the $k$th power of the adjacency matrix: https://en.wikipedia.org/wiki/Adjacency_matrix#Matrix_powers So if you calculate the pairwise distances for all nodes you can determine the number of paths of that length by powering the matrix, and in this way check uniqueness.
  • Alternatively, Dijkstra's algorithm can be modified to give the number of shortest paths. Instead of just keeping track of the distance, keep track of the number of paths that realize that distance.

Previously I wrote out a strategy using the first bullet (still in the answer history), but I think it would be horribly inefficient and better to do something like the following:

Iterate over the nodes of the graph, and for each node s do:

  • Use a modified Dijkstras algorithm (below) to check whether all the paths from it to other nodes are min unique.
  • If not, stop and reject the graph.
  • Otherwise, continue. (You can also remove s at this point.)

Modified Dijkstra:

  1. Run Dijkstra's algorithm to calculate all the distances $d(s,w)$ for $w \in V$. (Here $s$ is the fixed node from the above loop.)

  2. Then, for each node $w$ check whether there are $u,u' \sim w$ , $u \not = u'$, with $d(s,u) = d(s,w) - d(u,w)$ and $d(s,u') = d(s,w) - d(u',w)$. If there are any, then the graph is not min-unique and you can reject it.

If every $w$ passes this, then for all $w$, the minimum path from $s$ to $w$ is unique. Here is the reason: Suppose that there is a node $w$ where there are two paths from $s$ to $w$ of shortest length. Moreover, choose $w$ to be a closest node to $s$ satisfying this property. Let $\gamma, \gamma'$ be two of those paths. The nodes of $G$ that $\gamma, \gamma'$ step through right before $w$ have to be different, otherwise that node would be a node closer to $s$ with non-unique min paths. Say those nodes are $u,u'$. We must have $d(s,u) = d(s,w) - d(u,w)$ and $d(s,u') = d(s,w) - d(u',w)$, and $u,u' \sim w$ by construction, which means the test in the above loop would have caught this.

(Note something a little subtle here is that you need all $w$ to pass this test to say anything about any one of them.; e.g. imagine starting with a square with one node labelled $s$. Add a long path to the opposite node of $s$, say $t$, to form a lollipop. The test will only fail at $t$, although every node beyond $t$ has 2 min paths to $s$.)

This costs an extra additive $O(E)$ per loop. This is a little more expensive than Dijkstra, but perhaps you can squeeze the min uniqueness into the actually construction of the shortest paths tree. I would just use an out-of-the-box implementation of Dijkstra's algorithm and then run this extra step.

So that gives $O(V (D + E))$,where $D = O ( E + V log(V))$ is the time to run Dijkstra's algorithm. Since you're building a game for humans and not super computers, I guess $V$ is not that big and this is fine.

Let me know if anything is unclear or seems mistaken.


Maybe a reasonable thing to do would be to program a min-uniqueness checker along the above lines, then sample uniformly random points in a square and build the Delaunay triangulation, and check min-uniqueness. You can also download some small graph libraries, for instance through networkx, and run through them.

I don't know how often you'd have to repeat this until you find a min-unique graph. You can easily burn through millions of graphs this way, and maybe find a counter-example to the conjecture below.


If you allow the edge weights to be different : you take any connected graph and assign the edges random uniformly weights in $[0,1]$, and it will be min-unique.

You can even get away with assigning integer valued weights in $[0,N]$ if you choose $N$ judiciously, by an application of the isolation lemma: https://en.wikipedia.org/wiki/Isolation_lemma.

In the directed graph case this means that you can simulate min-unique distances by subdividing your edges, although you will end up with lots of degree 2 nodes this way. (This is part of why min-uniqueness is meaningful in complexity theory, since you can use this make a Turing machine unambiguous, see e.g here, which relates to the question of whether it is easier to solve problems where the unknown solution is known to be unique if it exists.)

In the undirected case it's not clear to me that obtaining min-uniqueness through subdivision works, however, since you have to also account for the pairs of new nodes and the choice of original node to connect to first along a path between pairs of new nodes complicates the reasoning.

Is it possible that for any graph $G$, there is a homeomorphic graph that is min-unique? I'm think this is likely to be false. I put a conjecture in the next section.


Observation: If G is an undirected, unweighted graph, then G is min-unique iff all the blocks of its block-cut tree are min-unique.

Proof: Suppose the blocks are min-unique. Consider any pair of vertices. There is a unique path in the block-cut tree, and within each block there is a unique min-path connecting the cut-vertices separating the blocks that the tree-path steps through. On the other hand, suppose that G is min-unique. The shortest paths connecting nodes of any of the biconnected blocks do not leave the block, since it would have to do so along it cut-vertex it would later have to return through, hence the block is also min-unique. QED

Using this, here are some classes of min-unique (unweighted, undirected) graphs: odd-cycles, complete graphs and, by the observation, graphs where the maximal 2-connected components are either odd cycles or complete graphs. The last class includes trees as the case where the blocks are edges.

Also, this observation means that to classify the min-unique graphs it suffices to classify the 2 vertex connected min-unique graphs.

Some doodling has lead me to believe the following:

Conjecture: The only 2-vertex connected, undirected, unweighted, min-unique graphs are odd cycles and complete graphs.

I'll update if I find a proof or a counter-example.

This would imply:

Conjecture: The only min-unique (undirected, unweighted) graphs are those whose biconnected components are either odd-cycles are complete graphs.

| cite | improve this answer | |
$\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.