<p>This sounds similar to <em>superbubbles</em> in bioinformatics.</p>

<p>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:</p>

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

<p>Onodera, Sadakane, and Shibuya: <strong>Detecting Superbubbles in Assembly Graphs</strong>. <a href="https://doi.org/10.1007/978-3-642-40453-5_26" rel="nofollow noreferrer">WABI 2013</a>, <a href="https://arxiv.org/abs/1307.7925" rel="nofollow noreferrer">arXiv</a>.</p>

CC BY-SA 3.0
2017-05-04T13:14:26.673Z
This is exactly what I was looking for, thanks a lot!
bartavelle
CC BY-SA 3.0
2017-05-03T17:13:16.043Z
2017-05-03T17:13:16.043Z
Jouni Sirén
<p>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?</p>

<p>EDIT: Hopefully more precisely, thanks to the comment:</p>

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

<ol>
<li>$\forall v \in H$, $v$ is reachable from $A$,</li>
<li>$\forall v \in H$, $B$ is reachable from $v$,</li>
<li>$\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$,</li>
<li>$\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$.</li>
</ol>

<p>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).</p>

<p>Illustration:</p>

<p>In <a href="https://www.projectaon.org/en/svg/lw/02fotw.svgz" rel="nofollow noreferrer">This graph</a>, the following graphs are examples of what I am looking for:</p>

<ul>
<li>$H(001,160)$, containing nodes $001, 160, 273$;</li>
<li>$H(160,300)$, containing nodes $160, 255, 203, 016, 048, 133, 268, 348, 333, 125, 067, 300$</li>
</ul>

<p>The subgraph between node $160$ and $333$ doesn't fit the bill.</p>

CC BY-SA 3.0
2017-05-02T02:33:53.420Z
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
CC BY-SA 3.0
2017-05-02T09:37:25.197Z
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
CC BY-SA 3.0
2017-05-02T09:46:59.697Z
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
CC BY-SA 3.0
2017-05-02T11:08:41.803Z
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
CC BY-SA 3.0
2017-05-02T11:11:40.960Z
I realized I also need be $H$ to be the smallest possible ... will update the question.
bartavelle
CC BY-SA 3.0
2017-05-02T11:19:30.853Z
Induced subgraph: if two vertices are in $H$ and there's an edge between them in $G$ then we keep the edge in $H$. If it's just "a subgraph" rather than "an induced subgraph" we can discard some of those edges. If $H$ is the smallest possible subgraph (induced or otherwise) which contains $A$ and $B$ and for which every vertex $v$ is on a path from $A$ to $B$ then it's just a single shortest path. Is that your intention?
Peter Taylor
CC BY-SA 3.0
2017-05-02T11:35:04.047Z
I am afraid I am not too good at this, I updated the question and added an example, hopefully making my intention clear.
bartavelle
CC BY-SA 3.0
2017-05-02T14:08:38.310Z
Your example looks like a [DAG](https://en.wikipedia.org/wiki/Directed_acyclic_graph). Is that always the case? It's also not clear to me how a subgraph minimizes distance. And it's odd that for you a "subgraph" is a set of vertices: do you mean the subgraph induced by the vertices (I don't think you ever answered Peter's question.)
Sasho Nikolov
CC BY-SA 3.0
2017-05-02T15:44:15.200Z
There are cycles in the graph i linked, and in the general case I work with directed graphs. As for the question, no, it's not the shortest path. I *think* I mean the graph induced by the listed vertices.
bartavelle
<graph-theory>
Is there a name for graph regions that lie between two nodes?
bartavelle
# Is there a name for graph regions that lie between two nodes?

(Asked by: username_0 on 2017-05-01)

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](https://www.projectaon.org/en/svg/lw/02fotw.svgz), 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.

**Tags:** graph-theory

> **Comments:**
> **username_1**: The union of all shortest paths from A to B is sometimes called an "interval", but it's not quite the same thing,  
> **username_2**: 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*".  
> **username_2**: 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$?  
> **username_0**: 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!  
> **username_0**: I realized I also need be $H$ to be the smallest possible ... will update the question.  
> **username_2**: Induced subgraph: if two vertices are in $H$ and there's an edge between them in $G$ then we keep the edge in $H$. If it's just "a subgraph" rather than "an induced subgraph" we can discard some of those edges. If $H$ is the smallest possible subgraph (induced or otherwise) which contains $A$ and $B$ and for which every vertex $v$ is on a path from $A$ to $B$ then it's just a single shortest path. Is that your intention?  
> **username_0**: I am afraid I am not too good at this, I updated the question and added an example, hopefully making my intention clear.  
> **username_3**: Your example looks like a [DAG](https://en.wikipedia.org/wiki/Directed_acyclic_graph). Is that always the case? It's also not clear to me how a subgraph minimizes distance. And it's odd that for you a "subgraph" is a set of vertices: do you mean the subgraph induced by the vertices (I don't think you ever answered Peter's question.)  
> **username_0**: There are cycles in the graph i linked, and in the general case I work with directed graphs. As for the question, no, it's not the shortest path. I *think* I mean the graph induced by the listed vertices.  

---

## 1 answers

### Answer by username_4 on 2017-05-03. Score: 3 | Accepted answer

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](https://doi.org/10.1007/978-3-642-40453-5_26), [arXiv](https://arxiv.org/abs/1307.7925).

> **Comments:**
> **username_0**: This is exactly what I was looking for, thanks a lot!  

---

