2004 | OriginalPaper | Chapter
Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems
Authors : E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan
Published in: Integer Programming and Combinatorial Optimization
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the problems of enumerating all minimal strongly connected subgraphs and all minimal dicuts of a given 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-complete 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.