McGill University - School of Computer Science

Algorithms Seminar 2004

Everybody is welcome!

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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at beezer at 
Web Address: