AG 1   Info

AG Audience

English

45 Minutes

Saarbrücken

We are investigating problems of the following type: given k pebbles (possibly of different colors) in a graph, move the pebbles (minimizing the total or maximum movement) such that the graph induced by the pebbles has a certain property. For example, this property can be connectivity, independence, red pebbles dominating the blue pebbles etc. We want to determine whether such a problem is fixed-parameter tractable parameterized by the number k of pebbles. For a general class of these problems (where the required property is closed under edge addition), we can characterize the parameterized complexity of the problem: fixed-parameter tractability essentially depends on the treewidth of the minimal good configurations. This general result can be used to determine the complexity of several concrete problems. We also investigate certain problem variants where the general result cannot be applied or better algorithms can be obtained by a direct approach.

It turns out that various well-known algorithmic techniques are relevant in this context as well.

Joint work with Erik D. Demaine and MohammadTaghi Hajiaghayi.

Rob van Stee

--email hidden

passcode not visible

logged in users only