A graph $G = (V, E)$, $S \subseteq V$, and requirements $r(u, v)$ for all $(u, v) \in V \times V$.
Output:
All minimal spanning graph $H$ of $G$ satisfying $\lambda^S_H \ge r(u, v) \; \forall (u, v) \in V \times V$.
Complexity:
Incremental polynomial time.
Comment:
The $S$-connectivity $\lambda^S_G(u, v)$ of $(u, v)$ in $G$ is the maximum number of $uv$-paths such that no two of them have an edge or a node in $S \setminus \{u, v\}$ in common. This complexity holds for edge-connectivity.