1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Chao Xu Oct 7 '16 at 20:52
  • $\begingroup$ 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). $\endgroup$ – Shahab Oct 10 '16 at 20:31
  • $\begingroup$ I see you are using the definitions in this paper, which defines a path completely differently from what I'm used to(the first comment). $\endgroup$ – Chao Xu Oct 11 '16 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.