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.

Improve this question
$\endgroup$
3
  • $\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, 2016 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, 2016 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, 2016 at 5:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.