DIMACS TR: 2003-35
On Enumerating Minimal Dicuts and Strongly Connected Subgraphs
Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan
ABSTRACT
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