P286: Enumeration of all minimal path conjunctions in a graph

P286: Enumeration of all minimal path conjunctions in a graph

Input:

A directed graph $G = (V, E)$, $s_1, s_2, t_1 \in V$, $T_2 \subseteq V$, and $\mathcal{P} = \{ (s_1, t_1)\} \cup \{(s_2, t): t\in T_2\}$.

Output:

All minimal path conjunctions in $G$.

Complexity:

Polynomial delay.

Comment:

A path conjunction is a edge subset $E' \subseteq E$ such that for all $(s, t) \in \mathcal{P}$, $s$ is connected to $t$ in the graph $G' = (V, E')$.

Reference:

[Boros2004a] (Bibtex)