P498: Enumeration of all minimal path-conjunctions of a directed graph.
P498: Enumeration of all minimal path-conjunctions 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-conjunctions of $G$ with respect to $\mathcal{P}$.
Complexity:
NP-hard.
Comment:
A minimal path-conjunction is a minimal set of edges $E'$ such that for all $i$, all vertices in $V_i$ belong to a connected component in $(V, E')$.