|DATE:||Wednesday, March 10th 2004.|
|TIME:||4:30 PM - 5:30 PM|
|TITLE:||On Enumerating Minimal Strongly Connected Subgraphs and Dicuts|
|SPEAKER:||Leonid Khachiyan, Rutgers University, NY.|
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 $A \subset R^n$, it is NP-hard to generate all maximal subsets of $A$ contained in a closed half-space through the origin. We also discuss the enumeration of all minimal subsets $X$ of $A$ such that $cone(X)=R^n$, and show that this problem includes as a special case the well-known hypergraph transversal problem.
Joint work with E. Boros, K. Elbassioni, and V. Gurvich.