DIMACS TR: 2003-35

On Enumerating Minimal Dicuts and Strongly Connected Subgraphs

Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan


We consider the problems of enumerating all minimal strongly connected subgraphs and all minimal dicuts of a given directed graph $\G$. 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-complete to tell whether it can be extended. The latter result implies, in particular, that for a given set of points $\cA\subseteq\RR^n$, it is NP-hard to generate all maximal subsets of $\cA$ contained in a closed half-space through the origin. We also discuss the enumeration of all minimal subsets of $\cA$ 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.

Paper available at ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-35.ps.gz
DIMACS Home Page