P500: Enumeration of all minimal path-disjunctions of a directed graph.
P500: Enumeration of all minimal path-disjunctions of a directed graph.
Input:
A directed graph $G = (V, E)$ and a family of pairs $\mathcal{P} = \binom{V_1}{2} \cup \dots \cup \binom{V_p}{2}$, where $V_1, \dots, V_p$ are disjoint vertex subset of $V$.
Output:
All minimal path-disjunctions of $G$.
Complexity:
NP-hard.
Comment:
A minimal path-disjunctions is a minimal set of edges $E'$ such that for some $i$, all vertices in $V_i$ belong to a connected component in $(V, E')$.