P499: Enumeration of all minimal path-conjunctions of a directed graph.

P499: Enumeration of all minimal path-conjunctions of a directed graph.

Input:

A directed graph $G = (V, E)$ and a family of pairs $\mathcal{P} = \{(s_1, t_1)\} \cup \{(s_2, t) \mid t \in T\}$, where $T \subseteq V$.

Output:

All minimal path-conjunctions of $G$.

Complexity:

Polynomial delay.

Comment:

A minimal path-conjunction is a minimal set of edges $E'$ such that any pair of vertices in $\mathcal{P}$ is connected in $(V, E')$.

Reference:

[Khachiyan2007] (Bibtex)