Find previous "chokepoint" in path

Question

I have a "tree"-like structure of nodes and I'm trying to figure out an algorithm that will find previous "chokepoint" when end node is given. Here is a picture to better demonstrate:

• So when 15 is specified as end node I want to find 7
• And if 7 is specified as end node I want to find 1
• But in the example above if anything else than 7,15 or 16 is specified as end node the found node is the previous one since that is the only node connecting to the end node.

So the node I am searching for is the previous node that all paths must go through to get to the end node.

I tried an algorithm where I start from the end node and go backwards (using Breadth-first) and every node I find that has 2 or more outputs I add to a new list and nodes with one output I skip. For example in case with 15 as the end node, I end up adding 10 and 7 to list of potential nodes, but I'm not sure how to from there. Since I should not continue traversing from 7.

Is there potentially an algorithm out there that already does that and if not how could I achieve this?

Answer 1

I believe your "choke points" are what is commonly known as "dominators". In a directed graph, one node X dominates another Y if all paths to Y must go through X. In your graph, 1 and 7 dominate all greater nodes.

See: https://en.wikipedia.org/wiki/Dominator_(graph_theory)

The dominators of a directed graph form a tree. The wikipedia article gives a simple algorithm for finding them all in quadratic time.

You can do it in linear time, but it's tricky. The classic algorithm is from Lengauer and Tarjan. You can find it here: https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf