<p>Is there a fast algorithm to detect possible bridge arcs in hyperpaths from set $S$ of nodes to node $t$ in a hypergraph $G$. That is, given a hypergraph $G$, source nodes $S$, and target node $t$, decide whether there exists a hyperarc $A=\langle X, y\rangle \in G$ so that removing $A$ makes target node $t$ unreachable from source nodes $S$.</p>

<p>I am using the usual notation of reachability in hypergraphs as follows: $t$ is reachable from $S$ if $t$ belongs to the minimum set $Z$ satisfying the two following conditions:</p>

<ul>
<li><p>$S \subseteq Z$</p></li>
<li><p>For all $\langle X, y \rangle \in G$, if $X \subseteq Z$ then $y \in Z$.</p></li>
</ul>

<p>Obviously, one can detect bridge arcs in quadratic time by first finding a path from $S$ to $t$ and, for each hyperarc in that path, checking in linear time if $t$ becomes unreachable from $S$ by removing that hypoerarc. I'm looking for anything that might improve on this quadratic upperbound.</p>

CC BY-SA 3.0
2016-10-07T20:52:58.887Z
Is the following (likely more intuitive) definition equivalent? $t$ is reachable from $S$ iff there exist a sequence of edges $\langle X_1, y_1 \rangle,\ldots,\langle X_n, y_n \rangle$ such that $X_1=S$, $y_n=t$ and $y_i\in X_{i+1}$ for all $i<n$?
Chao Xu
CC BY-SA 3.0
2016-10-10T20:31:18.647Z
No, your definition is not equivalent to reachability in hypergraphs. For one thing, $X_1 = S$ does not work. There might not be any hyperarc with sources $S$. Secondly, and more importantly, your definition does not assert any relation between $X_i$ and $X_{i+1}$. Essentially, nodes can be removed or added arbitrarily in your definition. Also, I don't understand why you think your definition is intuitive. What is the intuition behind it? Finally, the definition of reachability in hypergraphs (as I gave it) is pretty standard and intuitive to me (it's just a fixpoint operation).
Shahab
CC BY-SA 3.0
2016-10-11T05:38:08.547Z
I see you are using the definitions in [this paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.312), which defines a path completely differently from what I'm used to(the first comment).
Chao Xu
<graph-theory><graph-algorithms><hypergraphs>
Detecting bridges in Hypergraph S-t Reachability
Shahab
# Detecting bridges in Hypergraph S-t Reachability

(Asked by: username_0 on 2016-10-07)

Is there a fast algorithm to detect possible bridge arcs in hyperpaths from set $S$ of nodes to node $t$ in a hypergraph $G$. That is, given a hypergraph $G$, source nodes $S$, and target node $t$, decide whether there exists a hyperarc $A=\langle X, y\rangle \in G$ so that removing $A$ makes target node $t$ unreachable from source nodes $S$.

I am using the usual notation of reachability in hypergraphs as follows: $t$ is reachable from $S$ if $t$ belongs to the minimum set $Z$ satisfying the two following conditions:

* $S \subseteq Z$
* For all $\langle X, y \rangle \in G$, if $X \subseteq Z$ then $y \in Z$.

Obviously, one can detect bridge arcs in quadratic time by first finding a path from $S$ to $t$ and, for each hyperarc in that path, checking in linear time if $t$ becomes unreachable from $S$ by removing that hypoerarc. I'm looking for anything that might improve on this quadratic upperbound.

**Tags:** graph-theory, graph-algorithms, hypergraphs
> **Comments:**
> **username_1**: Is the following (likely more intuitive) definition equivalent? $t$ is reachable from $S$ iff there exist a sequence of edges $\langle X_1, y_1 \rangle,\ldots,\langle X_n, y_n \rangle$ such that $X_1=S$, $y_n=t$ and $y_i\in X_{i+1}$ for all $i<n$?  
> **username_0**: No, your definition is not equivalent to reachability in hypergraphs. For one thing, $X_1 = S$ does not work. There might not be any hyperarc with sources $S$. Secondly, and more importantly, your definition does not assert any relation between $X_i$ and $X_{i+1}$. Essentially, nodes can be removed or added arbitrarily in your definition. Also, I don't understand why you think your definition is intuitive. What is the intuition behind it? Finally, the definition of reachability in hypergraphs (as I gave it) is pretty standard and intuitive to me (it's just a fixpoint operation).  
> **username_1**: I see you are using the definitions in [this paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.312), which defines a path completely differently from what I'm used to(the first comment).  

---

## 0 answers

