Title: Graph Decompositions and Computation

Speaker: Blair Sullivan, Oak Ridge National Laboratory

Date/Time: November 9, 2010, 2:00 pm Pacific Time, 3:00pm Mountain Time        

Location: 915/S101 (Sandia CA), CSRI Building/Room 90 (Sandia NM) 

Brief Abstract: Advances in abstract graph theory during the last twenty years include the discovery of tree decompositions and branch decompositions.  Originally conceived as tools for proving the graph minors theorem, other researchers discovered that these decompositions provided a useful framework for dynamic programming.  A key measure of these decompositions is their width, as a large class of NP-hard problems can be solved to optimality via dynamic programming where the complexity is polynomial in the size of the graph, but exponential in the width. For example, given a graph and a tree decomposition of bounded width, many classic NP-complete problems such as Hamiltonian Circuit, Vertex Coloring, and Maximum Weighted Independent Set can be solved in time which is polynomial in the number of vertices. Significant effort has been put forth by the community in developing effective heuristics for finding low width tree and branch decompositions, as finding decompositions with optimal (minimum) width is NP-hard. We are developing new mathematical and computational techniques to leverage the graph-theoretic machinery of tree decompositions for large dataset analysis. The decompositions provide a natural partitioning of the graph for parallel computation, since they break the graph into overlapping pieces of bounded size which are associated with the nodes of a tree so that adjacent parts have pre-determined, well-understood interaction. This talk summarizes the work we have done in developing an open source software library for generating low width decompositions, as well as some initial results using these decompositions to solve maximum independent set.  We discuss relationships between numerical linear algebra routines and some of the heuristics for graph decompositions as well as thoughts and preliminary results on parallelization of these computations. This is joint work with Chris Groer (ORNL), and is supported by a grant from the Department of Energy's Applied Scientific Computing Research program.

CSRI POC: Ali Pinar, 925-294-4683