Abstract
We consider the problems of enumerating all minimal strongly connected subgraphs and all minimal dicuts of a given strongly connected directed graph G=(V,E). We show that the first of these problems can be solved in incremental polynomial time, while the second problem is NP-hard: given a collection of minimal dicuts for G, it is NP-hard to tell whether it can be extended. The latter result implies, in particular, that for a given set of points
$\mathcal{A}\subseteq\mathbb{R}^{n}$
, it is NP-hard to generate all maximal subsets of
$\mathcal{A}$
contained in a closed half-space through the origin. We also discuss the enumeration of all minimal subsets of
$\mathcal{A}$
whose convex hull contains the origin as an interior point, and show that this problem includes as a special case the well-known hypergraph transversal problem.