This interdisciplinary project will incorporate the disciplines of Computer Science and Mathematics. However the project is specifically housed within the Hope College Department of Computer Science.
This project will involve developing and testings algorithms for graph pebbling problems. A graph G = (V, E) is composed of a set of vertices, V, and a set of pairs of vertices, E, called edges. Two vertices of a graph are adjacent if they are connected by an edge. A pebbling configuration is a function C from vertices to non-negative integers, where C(v) is the number of pebbles on vertex v. For any vertex v such that C(v) is at least 2, a pebbling step consists of removing two pebbles from v and placing one pebble on a vertex adjacent to v. Thus, pebbles can be moved from one vertex to any adjacent vertex, but each time a pebble is moved, another pebble from that vertex is removed from the graph. A configuration is called r-solvable if there is a sequence of pebbling steps that places at least one pebble on a specified vertex r. We refer to the problem of determining whether or not a configuration is r-solvable as Reachable. A configuration is called solvable if it is r-solvable for every vertex in the graph—that is, if it is possible to place a pebble on any vertex of the graph using pebbling steps. This problem is referred to as Solvable.
There is no known efficient algorithm to solve either Reachable or Solvable. The goal of this project will be to create algorithms for these and other graph pebbling problems that are efficient for some classes of graphs or are more efficient than currently known algorithms.
The project will begin with an extensive review of the graph pebbling literature, with a particular focus on papers that discuss algorithms for graph pebbling problems.
Some background in programming, preferably Java, will be required. Preference will be given to candidates who have taken a course in algorithms, data structures, combinatorics, and/or graph theory.