Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Drew Sills, Rutgers University, asills {at} math [dot] rutgers [dot] edu
Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Pebble games for graph arboricity

Speaker: Ileana Streinu, Smith College & U. Mass Amherst

Date: March 31, 2005 4:30-5:30pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


The pebble game algorithm, invented by Hendrickson and Jacobs for the study of 2-dimensional generically rigid graphs, is an elegant and efficient paradigm underlying modern research on protein flexibility. We analyze extensions of the original algorithm to a family of pebble games induced by two parameters k and l. They characterize graphs which can be turned into edge-disjoint unions of k spanning trees via the addition of **ANY** l edges, and which satisfy hereditarily a linear inequality of the form m <= k(n-1) - l between the number of vertices and edges. They have well known matroidal properties for values of l in the interval [0,k) but not otherwise. In this setting, the "maximal components" are indicators of critical subgraphs for a variety of tasks, and correspond to rigid components in the protein flexibility applications. We show how to compute them efficiently and how to use them to obtain new algorithms for Henneberg sequences and edge-disjoint tree partitionings. As a side-effect we improve some other existing algorithms involving pseudo-triangulations. Along the way, the well known theorem of Tutte and Nash-Williams on edge-disjoint tree decompositions will be extended with a characterization via pebble games. I will use a variety of graphical props to illustrate the algorithms (presented indeed as "games") and some of their applications.

This is joint work with Audrey Lee and Louis Theran from University of Massachusetts at Amherst.