In mathematics and

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

, a pebble game is a type of

mathematical game A mathematical game is a game whose rules, strategies, and outcomes are defined by clear mathematical parameters. Often, such games have simple rules and match procedures, such as Tic-tac-toe and Dots and Boxes. Generally, mathematical games ne ...

played by placing "pebbles" or "markers" on a

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...

according to certain rules: * A given step of the game consists of either placing a pebble on an empty vertex or removing a pebble from a previously pebbled vertex. * A vertex may be pebbled only if all its predecessors have pebbles. * The objective of the game is to successively pebble each vertex of ''G'' (in any order) while minimizing the number of pebbles that are ever on the graph simultaneously.

Running time

The trivial solution is to pebble an ''n''-vertex graph in ''n'' steps using ''n'' pebbles. Hopcroft, Paul and Valiant showed that any vertex of an ''n''-vertex graph can be pebbled with O(''n''/log ''n'') pebbles where the constant depends on the maximum in-degree. This enabled them to prove that

DTIME In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would ta ...

(''f''(''n'')) is contained in

DSPACE DSpace is an open source repository software package typically used for creating open access repositories for scholarly and/or published digital content. While DSpace shares some feature overlap with content management systems and document managem ...

(''f''(''n'')/log ''f''(''n'')) for all time-constructible ''f''. Lipton and Tarjan showed that any ''n''-vertex planar acyclic

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...

with maximum in-degree ''k'' can be pebbled using O( + ''k'' log₂ ''n'') pebbles. They also proved that it is possible to obtain a substantial reduction in pebbles while preserving a polynomial bound on the number of pebbling steps with a theorem that any ''n''-vertex planar acyclic directed graph with maximum in-degree ''k'' can be pebbled using O(''n''^2/3 + ''k'') pebbles in O(''n''^5/3) time. Alon, Seymour and Thomas showed that any ''n''-vertex acyclic directed graph with no ''k''_''h''- minor and with maximum in-degree ''k'' can be pebbled using O(''h''^3/2 ''n''^1/2 + ''k'' log ''n'') pebbles.

Variations

An extension of this game, known as "black-white pebbling", was developed by

Stephen Cook Stephen Arthur Cook (born December 14, 1939) is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor at the Univ ...

and Ravi Sethi in a 1976 paper. It also adds white pebbles, which may be placed at any vertex at will, but can only be removed if all the vertex's immediate ancestor vertices are also pebbled. The goal remains to place a black pebble on the target vertex, but the pebbling of adjacent vertices may be done with pebbles of either color. Takumi Kasai ''et al.'' developed a game in which a pebble may be moved along an edge-arrow to an unoccupied vertex only if a second pebble is located at a third, control vertex; the goal is to move a pebble to a target vertex. This variation makes the pebble game into a generalization of games such as Chinese checkers and

Halma Halma (from the Greek word ἅλμα meaning "jump") is a strategy board game invented in 1883 or 1884 by George Howard Monks, an American thoracic surgeon at Harvard Medical School. His inspiration was the English game ''Hoppity'' which was d ...

. They determined the

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

of the one-player and two-player versions of this game, and special cases thereof. In the two-player version, the players take turns moving pebbles. There may also be constraints on which pebbles a player can move. Pebbling may be used to extend Ehrenfeucht–Fraïssé games.

Running time

Variations

See also

References

Further reading