## Dec 2, 2016:

#
Pebble Game Algorithms and Sparse Graphs

## Authors: Audrey Lee, Ileana Streinu

##
Speaker: Elham Havvaei

A graph is (k,l)-sparse if the number of induced edges in any
nonempty subgraph with n' vertices is at most kn'-l. Testing (k,l)-sparsity
can be performed in polynomial time when k and l are integers and
0 ≤ l < 2k via a family of mathematical games called the
(k,l)-pebble games. Pebble game is played by moving "pebbles" or
"markers" on a directed graph according to certain rules.