Connectivity of Graphs Under Edge Flips

Authors: 

Norbert Zeh

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2

Abstract: 

We study the following problem: Given a set V of n vertices and a set E of m edge pairs, we define a graph family G(V,E) as the set of graphs that have vertex set V and contain exactly one edge from each pair in E. We want to find a graph in G(V,E) that has the minimal number of connected components. We show that, if the edge pairs in E are non-disjoint, the problem is NP-hard. This is true even if an edge is not allowed to appear in more than two edge pairs and the union of all graphs in G(V,E) is planar. If the edge pairs are disjoint, we provide an O(n^2m)-time algorithm that finds a graph in G(V,E) with the minimal number of connected components. Our proof of the latter statement is obtained using the concept of flipping edges in the graphs in G(V,E), where a flip in a graph G in G(V,E) removes an edge e of G and replaces it with the other edge in the pair in E that contains e. We answer the following questions: Can every graph in G(V,E) be transformed into a graph in G(V,E) with the minimal number of connected components using a sequence of edge flips that steadily decrease the number of connected components in the graph? How long is the shortest such sequence (that is, how many flips are in this sequence)? Can we transform any graph in G(V,E) with at most k connected components into any other graph in G(V,E) with at most k connected components using a sequence of edge flips that never increase the number of connected components beyond k? How long does such a sequence have to be?

Tech Report Number: 
CS-2003-07
Report Date: 
September 15, 2003
AttachmentSize
PDF icon CS-2003-07.pdf2.22 MB