TIME: Wed, April 25, 1:30pm
PLACE: Room 5115 Herzberg
SPEAKER: Norbert Zeh
TITLE: Connectivity of graphs under edge flips

ABSTRACT: Given a vertex set V and a collection E of edge pairs, the graph
family G(V,E) is the set of graphs with vertex set V and containing exactly
one edge from each pair in E.  Our goal is to find a graph in G(V,E) with the
minimum number of connected components.  This problem is motivated by a
problem in computational topology.  We show that, in general, the problem is
NP-hard.  We also show that for two particular kinds of sets E, one of which
is the one arising in the motivating topological problem, we can find a graph
in G(V,E) with the minimum number of connected components in O(nm) time, where
n = |V| and m = |E|.