DATE: | Wednesday, March 10th 2004. |
TIME: | 4:30 PM - 5:30 PM |
PLACE: | McConnel 320 |
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.