# Is there a name for graph regions that lie between two nodes?

Perhaps a bit more formally, is there a name for regions delimited by nodes A and B, in a directed graph, where all paths starting from A, when prolonged, will eventually reach B, and all paths reaching B are crossing A, or start from a node that is reachable from A?

EDIT: Hopefully more precisely, thanks to the comment:

I am interested in subgraphs $H(A,B)$ of $G$, with $A \in G, B \in G$:

1. $\forall v \in H$, $v$ is reachable from $A$,
2. $\forall v \in H$, $B$ is reachable from $v$,
3. $\forall x \in G, x \notin H, v \in H$, if $v$ is reachable from $x$, then all paths between $x$ and $v$ must cross $A$,
4. $\forall x \in G, x \notin H, v \in H$, if $x$ is reachable from $v$, then all paths between $v$ and $x$ must cross $B$.

Given a node $A$, there can be several valid subgraphs $H(A,B)$. In the set of all valid subgraphs, I am interested in the one that minimizes the distance between $A$ and $B$ (I believe it unique in my use case).

Illustration:

In This graph, the following graphs are examples of what I am looking for:

• $H(001,160)$, containing nodes $001, 160, 273$;
• $H(160,300)$, containing nodes $160, 255, 203, 016, 048, 133, 268, 348, 333, 125, 067, 300$

The subgraph between node $160$ and $333$ doesn't fit the bill.

• The union of all shortest paths from A to B is sometimes called an "interval", but it's not quite the same thing, – David Eppstein May 2 '17 at 2:33
• Firstly, what is a "region" here? Obviously it's a subgraph, but is it an induced subgraph? Secondly, if the original graph is $G$ and the "region" is $H$, are the quantifiers over $G$ or $H$? In other words, does "all paths starting from A..." mean all paths in $G$ or all paths in $H$? Similarly "all paths reaching B". – Peter Taylor May 2 '17 at 9:37
• Followup which occurs to me: if $H$ is an induced subgraph then I think the first condition would be that if vertex $v \in H$ is reachable from $A$ then $B$ is reachable from $v$, and the second condition would be that if $B$ is reachable from $v$ then $v$ is reachable from $A$. But the title of this question says "that lie between two nodes". Is the intention really that every $v \in H$ should be reachable from $A$ and $B$ should be reachable from $v$? – Peter Taylor May 2 '17 at 9:46
• I am not knowledgeable enough with graph theory to know what an induced subgraph is. However, your second definition seems to fit what I want! – bartavelle May 2 '17 at 11:08
• I realized I also need be $H$ to be the smallest possible ... will update the question. – bartavelle May 2 '17 at 11:11

This sounds similar to superbubbles in bioinformatics.

We have a directed graph $G = (V, E)$. A superbubble is an induced subgraph defined by vertices $s, t \in V$ (with $s \ne t$). We have the following requirements:

• Vertex $t$ is reachable from $s$.
• The subgraph is induced by the set of vertices $U \subseteq V$ reachable from $s$ without passing through (first entering and then leaving) $t$.
• $U$ is also the set of vertices from which $t$ is reachable without passing through $s$.
• The subgraph is acyclic.
• The superbubble is minimal: no other vertex $t' \in U$ (with $t' \ne t$) defines a superbubble with vertex $s$.

Onodera, Sadakane, and Shibuya: Detecting Superbubbles in Assembly Graphs. WABI 2013, arXiv.

• This is exactly what I was looking for, thanks a lot! – bartavelle May 4 '17 at 13:14