-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The union of all shortest paths from A to B is sometimes called an "interval", but it's not quite the same thing, $\endgroup$ – David Eppstein May 2 '17 at 2:33
  • $\begingroup$ 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". $\endgroup$ – Peter Taylor May 2 '17 at 9:37
  • 1
    $\begingroup$ 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$? $\endgroup$ – Peter Taylor May 2 '17 at 9:46
  • $\begingroup$ 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! $\endgroup$ – bartavelle May 2 '17 at 11:08
  • $\begingroup$ I realized I also need be $H$ to be the smallest possible ... will update the question. $\endgroup$ – bartavelle May 2 '17 at 11:11
3
$\begingroup$

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.

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

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.