Consider the problem whose instance is a directed graph with the selected vertex V and k of 'pebbles'. We can in any order, perform the following elemental steps:
- on top of x we can put a pebble, if at a given moment are pebbles at all predecessors, of which leads edge to the x
- pebble placed on vertex you can remove (and reuse later).
The question is whether there exists a sequence of steps in which we put a pebble on the specified vertex v.
Can anyone prove that the problem is in PSPACE, please?