---
abstract: 'When a large collection of objects (e.g., robots, sensors, etc.) has to be deployed in a given environment, it is often required to plan a coordinated motion of the objects from their initial position to a final configuration enjoying some global property. In such a scenario, the problem of minimizing some function of the distance travelled, and therefore energy consumption, is of vital importance. In this paper we study several motion planning problems that arise when the objects must be moved on a graph, in order to reach certain goals which are of interest for several network applications. Among the others, these goals include broadcasting messages and forming connected or interference-free networks. We study these problems with the aim of minimizing a number of natural measures such as the average/overall distance travelled, the maximum distance travelled, or the number of objects that need to be moved. To this respect, we provide several approximability and inapproximability results, most of which are tight.'
author:
- Davide Bilò
- Luciano Gualà
- Stefano Leucci
- Guido Proietti
date: 'Received: date / Accepted: date'
title: 'Exact and approximate algorithms for movement problems on (special classes of) graphs [^1] [^2] '
---

Introduction
============

In many practical applications a number of centrally controlled objects need to be moved in a given environment in order to complete some task. Problems of this kind often occur in robot motion planning where we seek to move a set of robots from their starting position to a set of ending positions such that a certain property is satisfied. For example, if the robots are equipped with a short range communication device we might want to move them so that a message originating from one of the robots can be routed to all the others. If the robots’ goal is to monitor a certain area we might want to move them so that they are not too close to each other. Other interesting problems include gathering (placing robots next to each other), monitoring of traffic between two locations, building interference-free networks, and so on. To make things harder, objects to be moved are often equipped with a limited supply of energy. Preserving energy is a critical problem in ad-hoc networking, and movements are expensive. To prolong the lifetime of the objects we seek to minimize the energy consumed during movements and thus the distance travelled. Sometimes, instead, movements are cheap but before and/or after an object moves it needs to perform expensive operations. In this scenario we might be interested in moving the minimum number of objects needed to reach the goal.

In this paper, we assume the underlying environment is actually a *network*, which can be modelled as an undirected graph $G$, and the moving objects are centrally controlled *pebbles* that are initially placed on vertices of $G$, and that can be moved to other vertices by traversing the graph edges. To this respect, we study several movement planning problems that arise by various combinations of final positioning goals and movement optimization measures. In particular, we focus our study on the scenarios where we want the pebbles to be moved to a *connected subgraph* ([$\textsc{Con}$]{}), an *independent set* ([$\textsc{Ind}$]{}), or a *clique* ([$\textsc{Clique}$]{}) of $G$, while minimizing either the *overall movement* ([$\textsc{Sum}$]{}), the *maximum movement* ([$\textsc{Max}$]{}), or the *number of moved pebbles* ([$\textsc{Num}$]{}). We also give some preliminary results on the problem of moving the pebbles to an *s-t-cut*, i.e., a set of vertices whose removal makes two given vertices $s,t$ disconnected ([$s\mbox{-}t\mbox{-}\textsc{Cut}$]{}) while minimizing the above measures.

We will denote each of the above problems with $\psi$-$c$, where $\psi$ represents the goal to be achieved and $c$ the measure to be minimized. For a more rigorous definition of the problems we refer the reader to Section \[sec:formal\_definition\].

#### Related work.

Although movement problems were deeply investigated in a distributed setting (see [@PS06] for a survey), quite surprisingly the centralized counterpart has received attention from the scientific community only in the last few years.

The first paper which defines and studies these problems in this latter setting is [@demaine2007minimizing]. In their work, the authors study the problem of moving the pebbles on a graph $G$ of $n$ vertices so that their final positions form a *connected component*, a *path* (directed or undirected) *between two specified nodes*, an *independent set*, or a *matching* (two pebbles are matched together if their distance is exactly $1$).

Regarding connectivity problems, in [@demaine2007minimizing] the authors show that all the variants are hard and that the approximation ratio of ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Max}}}$ is between $2$ and ${\ensuremath{O}}(1+\sqrt{k/c^*})$, where $k$ is the number of pebbles and $c^*$ denotes the measure of an optimal solution. This result has been improved in [@berman2011], where the authors show that ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Max}}}$ can be approximated within a constant factor. In [@demaine2007minimizing] it is also shown that ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Sum}}}$ and ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Num}}}$ are not approximable within ${\ensuremath{O}}(n^{1-\epsilon})$ (for any positive $\epsilon$) and $o(\log n)$, respectively, while they admit approximation algorithms with ratios of ${\ensuremath{O}}(\min\{n \log n, k\})$ and ${\ensuremath{O}}(k^\epsilon)$, respectively. Moreover, the authors also provide an exact polynomial-time algorithm for ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Max}}}$ on trees.

Concerning independency problems, in [@demaine2007minimizing] the authors remark that it is [$\textsf{\upshape NP}$]{}-hard even to find any feasible solution on general graphs since it would require to find an independent set of size at least $k$. This clearly holds for all three objective functions. For this reason, they study an Euclidean variant of these problems where pebbles have to be moved on a plane so that their pairwise distances are strictly greater than $1$. In this case, the authors provide an approximation algorithm that guarantees an additive error of at most $1+1/\sqrt{3}$ for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$, and a polynomial time approximation scheme for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Num}}}$.

More recently, in [@friggstad2011minimizing], a variant of the classical facility location problem has been studied. This variant, called *mobile facility location*, can be modelled as a movement problem and is approximable within $(3+\epsilon)$ (for any constant $\epsilon>0$) if we seek to minimize the total movement [@ahmadian2013local], while the variant where the maximum movement has to be minimized admits a tight $2$-approximation [@demaine2007minimizing; @friggstad2011minimizing]. Moreover, as it is frequent in the practice to have a small number of pebbles compared to the size of the environment (i.e., the vertices of the graph), the authors of [@demaine2009FPT] turn to study fixed-parameter tractability. They show a relation between the complexity of the problems and their *minimal configurations* (sets of final positions of the pebbles that correspond to feasible solutions, such that any removal of an edge makes them unacceptable). Finally, we mention that in [@BDGMPW13] it was considered a set of vertex-to-vertex motion planning problems in a simple polygon, with the aim of forming final configurations enjoying some sort of *visual connectivity* among the pebbles.

#### Our results.

We start by studying connectivity motions problems in the case where pebbles move on a tree, and we devise two polynomial-time dynamic programming algorithms for ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Sum}}}$ and ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Num}}}$. These algorithms complement the already known polynomial-time algorithm for ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Max}}}$ on trees shown in [@demaine2007minimizing].

Then, we study independency motion problems on graphs where a *maximum independent set* (and thus a feasible solution for the corresponding motion problem) can be computed in polynomial time. This class of graphs includes, for example, perfect and claw-free graphs. More precisely, we show that ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ are [$\textsf{\upshape NP}$]{}-hard even on bipartite graphs (which are known to be perfect graphs [@bollobas1998modern]). Moreover, we devise three exact polynomial-time algorithms: one for solving ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on paths, and the other two for solving ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ and ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Num}}}$ on trees, respectively. Moreover, we devise a polynomial-time approximation algorithm for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ which is optimal unless an additive term of $1$ (this is clearly tight).

Concerning the problem of moving pebbles towards a clique of a general graph, we prove that all the three variants are [$\textsf{\upshape NP}$]{}-hard. Then, we provide an approximation algorithm for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Max}}}$ which is optimal unless an additive term of $1$ (this result is clearly tight). Moreover, we show that both ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$ and ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ are approximable within a factor of $2$, but they are not approximable within a factor better than $10\sqrt{5}-21 > 1.3606$, unless ${\ensuremath{\textsf{\upshape P}}}={\ensuremath{\textsf{\upshape NP}}}$. If the *unique game conjecture* [@khot2002power] is true, then both problems are not approximable within a factor better than $2$ and the provided approximation algorithms are tight. These results are obtained by showing a non-trivial relation with the *minimum vertex cover* problem. We also show that an exact solution for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ can be computed in polynomial time on every class of graphs for which finding a *maximum-weight clique* requires polynomial time (these classes of graphs also include perfect and claw-free graphs).

Finally, we present a strong inapproximability results of $\Omega(n^{1-\epsilon})$ (for any $\epsilon>0$) for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$, unless ${\ensuremath{\textsf{\upshape P}}}={\ensuremath{\textsf{\upshape NP}}}$, along with two approximation algorithms. The approximation algorithm for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ is essentially tight, while we show that any constant-factor approximation for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Num}}}$ would imply a tight approximation for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$.

The paper is organized as follows: in Section \[sec:formal\_definition\] we provide a formal definition of our problems, while in Sections \[sec:con\]–\[sec:stcut\] we give our results for [$\textsc{Con}$]{}, [$\textsc{Ind}$]{}, [$\textsc{Clique}$]{}, and [$s\mbox{-}t\mbox{-}\textsc{Cut}$]{}, respectively (for a summary of the state of the art of the studied problems, along with the results presented in this paper, see Table \[table:results\]). Finally, Section \[sec:concl\] concludes the paper.

[|c|M|L|M|]{} & ${\ensuremath{\textsc{Max}}}$ & ${\ensuremath{\textsc{Sum}}}$ & ${\ensuremath{\textsc{Num}}}$\
${\ensuremath{\textsc{Con}}}$ & G: $2 \le \rho = {\ensuremath{O}}(1)$ [@demaine2007minimizing; @berman2011] T: polynomial [@demaine2007minimizing] & G: $\rho = \Omega(n^{1-\epsilon})$ [@demaine2007minimizing] $\rho={\ensuremath{O}}(\min\{n \log n,k\})\!$ [@demaine2007minimizing] **T: polynomial** & G: $\rho=\Omega(\log n)$ [@demaine2007minimizing] $\rho={\ensuremath{O}}(k^\epsilon)$ [@demaine2007minimizing] **T: polynomial**\
${\ensuremath{\textsc{Ind}}}$ & G: [$\textsf{\upshape NP}$]{}-hard [@demaine2007minimizing] **IS:** [$c^* + 1$]{}**,** [$\rho \le 2$]{} **B:** [$\rho \ge 2$]{} **P: polynomial** & G: [$\textsf{\upshape NP}$]{}-hard [@demaine2007minimizing] **B: [$\textsf{\upshape NP}$]{}-hard** **T: polynomial** & G: [$\textsf{\upshape NP}$]{}-hard [@demaine2007minimizing] **T: polynomial**\
${\ensuremath{\textsc{Clique}}}$ & **G: [$\textsf{\upshape NP}$]{}-hard** & **G:** [$10\sqrt{5}-21 \le \rho \le 2$]{} & **G:** [$10\sqrt{5}-21 \le \rho \le 2$]{} **MWC: polynomial**\
${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$ & **G:** [$\rho = \Omega(n^{1-\epsilon})$]{} & **G:** [$\rho = \Omega(n^{1-\epsilon})$]{} & **G:** **$\rho$-apx $\Longrightarrow (\rho \cdot d)$-apx for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$**\

 \
 \
\[table:results\]

Formal definitions {#sec:formal_definition}
==================

A pebble motion problem, denoted by $\psi$-$c$, is an optimization problem whose instances consist of a loop-free connected undirected graph $G=(V(G),E(G))$ on $n$ nodes, a set $P=[k]=\{1,\dots, k\}$ of *pebbles*, a function $\sigma : P \to V(G)$ that assigns each pebble to a *start vertex* of $G$, and a boolean predicate $\psi : 2^{V(G)} \to \{ {\ensuremath{\texttt{True}}},{\ensuremath{\texttt{False}}}\}$ that assigns a truth value to every possible subset of vertices of $G$.

A (feasible) solution is a function $\mu : P \to V(G)$ that maps each pebble to an *end vertex* of $G$ (in other words, *moves* a pebble from its start to its end position) such that $\psi(\mu[P])$ is true, where $\mu[P]$ denotes the image of $P$ under $\mu$. Notice that, in general, it is not required for $\sigma$ or $\mu$ to be injective and thus we allow more than one pebble to be placed on the same vertex. In the rest of the paper, we will assume that a pebble moving from a vertex $u$ to a vertex $v$ always uses a *shortest path* in $G$ between $u$ and $v$, say $\pi_G(u,v)$. Moreover we denote by $d_G(u,v)$ the length of such a path. Finally, $c(\mu) \in \mathbb{N}_0$ is a measure function that assigns a non-negative integer to each feasible solution (i.e., to each set of moves). A solution $\mu^*$ that minimizes $c$ is said to be *optimal*.

In the following, we will study some of the movement problems that arise from the different choices of predicates and measures. In particular, we will consider the following predicates:

*Connectivity:*

:   ${\ensuremath{\textsc{Con}}}(U)$ is true if and only if the subgraph of $G$ induced by the set of vertices $U \subseteq V(G)$ is connected;

*Independency:*

:   ${\ensuremath{\textsc{Ind}}}(U)$ is true if and only if $U \subseteq V(G)$ is an independent set of $G$ of size $k$, i.e., there is at most one pebble per vertex and no two pebbles are on adjacent vertices;

*Clique:*

:   ${\ensuremath{\textsc{Clique}}}(U)$ is true if and only if $U  \subseteq V(G)$ induces a clique in $G$, i.e., for each pair $u,v$ of distinct vertices in $U$ there exists the edge $(u,v) \in E(G)$;

*$s$-$t$-Cut:*

:   Given $s,t \in V(G)$ with $s \not= t$, then ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}(U)$ is true if and only if $s \not \in U$, $t \not\in U$ and $U  \subseteq V(G)$ is an *s-t*-cut (i.e., there exists no path between $s$ and $t$ in the graph induced by the vertices in $V(G) \setminus U$);

and the following measures:

*Overall movement:*

:   The sum of the distances travelled by pebbles has to be minimized: every pebble $p \in P$ moves from its starting vertex $\sigma(p)$ to his end vertex $\mu(p)$, so the overall distance is ${\ensuremath{\textsc{Sum}}}(\mu) = \sum_{p\in P} d_G( \sigma(p), \mu(p) )$;

*Maximum movement:*

:   We want to minimize the maximum distance travelled by a pebble, i.e., the measure ${\ensuremath{\textsc{Max}}}(\mu)= \max_{p \in P} d_G( \sigma(p), \mu(p) )$;

*Number of moved pebbles:*

:   We aim to minimize the number of pebbles that need to be moved from their starting positions. The associated measure is ${\ensuremath{\textsc{Num}}}(\mu) = | \{ p \in P : \sigma(p) \not= \mu(p)\} |$.

Connectivity motion problems {#sec:con}
============================

In this section we describe two polynomial-time algorithms for solving on trees ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Sum}}}$ and ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Num}}}$, respectively. In this way we complement the result provided in [@demaine2007minimizing] for ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Max}}}$ on trees.

Solving ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Sum}}}$ on trees {#sec:con_sum_trees}
----------------------------------------------------------------------------

Our dynamic-programming algorithm relies on the following property of optimal solutions:

\[lemma:sum\_tree\_no\_crossing\] In any optimal solution $\mu^*$ for an instance of ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Sum}}}$ on trees, there exists no edge that is traversed in opposite directions by pebbles.

Let $\pi_G(u,v)$ denote a shortest path in $G$ between the vertices $u$ and $v$. Suppose by contradiction that there exists an optimal solution $\mu^*$, an edge $(x,y) \in E(G)$, and two pebbles $p, q \in P$ such that $p$ moves through the path $\pi_G(\sigma(p), x) \cup \{ (x,y) \} \cup \pi_G(y, \mu^*(p))$ and $q$ moves through the path $\pi_G(\sigma(q), y) \cup \{ (y,x) \} \cup \pi_G(x, \mu^*(q))$. Consider the solution $\mu^\prime$ obtained from $\mu^*$ by swapping the final positions for $p$ and $q$, i.e., $\mu^\prime(p)=\mu^*(q)$ and $\mu^\prime(q)=\mu^*(p)$. Clearly $\mu^\prime[P]=\mu^*[P]$, therefore $\mu^\prime$ is feasible. Moreover $c(\mu^\prime) < c(\mu^*)$ as we can move $p$ through the path $\pi_G(\sigma(p), x) \cup \pi_G(x,\mu^\prime(p))$ and $q$ through the path $\pi_G(\sigma(q), y) \cup \pi_G(y, \mu^\prime(q))$, thus saving $2$.

The algorithm first guesses a vertex $r \in V(G)$ such that there exists an optimal solution that places a pebble on $r$, then roots the tree $G$ at $r$ to obtain a rooted tree $G_r$, and finally considers all the subtrees of $G_r$ in a bottom-up fashion.

For a given subtree $T_u$ of $G_r$ rooted at the vertex $u$, let us denote by $\eta(u)$ the number of pebbles placed on $V(T_u)$ w.r.t. $\sigma$. When the subtree $T_u$ is examined, we consider an auxiliary problem. In this problem we want to place exactly $j \le k$ of the pebbles on the vertices of $T_u$ in order to satisfy the following properties:

1.  \[it:con\_P1\] the subgraph of $T_u$ induced by the final positions of the pebbles must be connected;

2.  \[it:con\_P2\] if $j \ge 1$ then at least one pebble must be placed on $u$.

Moreover, if $j < \eta(u)$ we want to move the $\eta(u)-j$ exceeding pebbles to the parent of $u$ (and thus outside $T_u$). In a similar manner, if $j > \eta(u)$ then the $j-\eta(u)$ missing pebbles are to be moved into $T_u$ from the parent of $u$, where we assume they are initially placed. We point out that, by Lemma \[lemma:sum\_tree\_no\_crossing\], we do not need to consider the case where some pebbles move into $T_u$ while others move out of $T_u$.

![Left: an instance of ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Sum}}}$ and its optimal solution. A single pebble is placed on each black vertex while the optimal movements are denoted by arrows. Right: the auxiliary problems corresponding to the optimal solution which are considered by the dynamic-programming algorithm.[]{data-label="fig:mov_con_sum"}](Fig1.eps)

We will denote by ${\ensuremath{\texttt{Opt}}}[u,j]$ the cost of the optimal movement for this auxiliary problem. Notice that, in ${\ensuremath{\texttt{Opt}}}[u,j]$, we are accounting for the cost of traversing all the edges of $T_u$ plus the edge from $u$ to its parent. To solve the original problem we need to find a solution corresponding to ${\ensuremath{\texttt{Opt}}}[r,k]$. Clearly as $k=\eta(r)$ we do not have exceeding or missing pebbles, in this case. We now show how to combine these auxiliary problems.

If $u$ is a leaf of $G_r$ then ${\ensuremath{\texttt{Opt}}}[u,j]=|\eta(u) - j|$. Otherwise, if $u$ is not a leaf, we can distinguish two cases: $j=0$ and $j > 0$. If $j=0$ then no pebble can be placed on $u$ or in any descendant of $u$, therefore all the pebbles must first be moved towards $u$ and then to the parent of $u$. Let $v_1, \dots, v_\ell$ be the set of children of $u$ in $G_r$, we have: ${\ensuremath{\texttt{Opt}}}[u,0] = \eta(u) + \sum_{i=1}^\ell {\ensuremath{\texttt{Opt}}}[v_i, 0]$.

Otherwise, if $j > 0$, we can move any number of pebbles between $1$ and $j$ to $u$, and place the remaining pebbles on the subtrees rooted at the children of $u$. Therefore we have: $${\ensuremath{\texttt{Opt}}}[u,j] = |\eta(u)-j| + \min_{ \substack{0 \le j_1, \dots, j_\ell < j \\ \sum_{i=1}^{\ell} j_i < j } } \left\{ \sum_{i=1}^{\ell} {\ensuremath{\texttt{Opt}}}[v_i, j_i] \right\} \mbox{.}$$

Notice that the minimum considers all the possible ways for distributing less than $j$ pebbles on the subtrees, i.e., all the vectors $(j_i)_i$ of $\ell$ elements whose sum is less than $j$.

We now argue on the fact that, despite the number of such vectors can be exponential on $j$, the minimum can be found in polynomial time.

This can again be done by using dynamic programming: let ${\ensuremath{\texttt{Min}}}[i,h]$ denote the minimum cost of placing $h$ pebbles in the first $i$ subtrees. Clearly when $i=1$ we have ${\ensuremath{\texttt{Min}}}[1, h] = {\ensuremath{\texttt{Opt}}}[v_1, h]$, while for $i > 1$ the following holds: $${\ensuremath{\texttt{Min}}}[i, h] = \min_{0 \le z \le h} \left\{ {\ensuremath{\texttt{Min}}}[i-1, z] + {\ensuremath{\texttt{Opt}}}[v_i, h-z] \right\} \mbox{.}$$

Therefore, the equation for ${\ensuremath{\texttt{Opt}}}[u,j]$ can be rewritten as: $${\ensuremath{\texttt{Opt}}}[u,j] = |\eta(u)-j| + \min_{0 \le i < j} {\ensuremath{\texttt{Min}}}[\ell, i] \mbox{.}$$

Notice how this way of distributing the pebbles is general and does not depend on the specific movement problem: in fact, it can be used every time we are interested in minimizing the cost of distributing a number of items in a set of bins if, for each bin, we incur a cost that depends on the number of items placed therein.

An example of an optimal decomposition into subproblems along with the corresponding optimal solution is shown in Figure \[fig:mov\_con\_sum\].

Regarding the complexity of the algorithm, the time required to compute a specific ${\ensuremath{\texttt{Opt}}}[u,j]$ is $O(\ell \cdot j) = O(\ell \cdot k)$. As the sum of the $\ell$-values over all the vertices is $n-1$, the time needed to compute ${\ensuremath{\texttt{Opt}}}[v,j]$ for a fixed $j$ and all $v \in V$ is $O(n \cdot k)$. It follows that all the possible subproblems can be solved in time $O(n \cdot k^2)$.

As we have to guess the vertex $r$, a naïve strategy would be repeating the above procedure $n$ times, one for each vertex of $G$. This would require an overall time of $O(n^2 \cdot k^2)$. We can do better by using a more sophisticated approach: consider a *centroid*[^3] $v$ of $G$, and notice that either there exists an optimal solution that places a pebble on $v$, or every optimal solution places all the pebbles on a single connected component of $G-v$. We first apply the above algorithm using $v$ as the root and then we proceed recursively on the trees of the forest $G-v$ (each of which has at most half of the vertices). More precisely, for every subtree $T$ of $G-v$, rooted at $v^\prime$, we recursively solve an instance consisting of the tree $T$ where all the pebbles in $V(T)$ are left unmoved and all pebbles not in $V(T)$ have been moved to $v^\prime$. This movement cost, i.e., $\sum_{p \in P : \sigma(p) \not\in V(T)} d(\sigma(p), v^\prime)$, is then added to the measure of the solution returned by the recursive call. Among all the computed solutions we choose the cheapest one.

By doing so, we are able to reduce the computational complexity to $O(n \cdot k^2 \log n)$. Indeed, the recurrence relation describing the running time of the algorithm is $T(n) = \sum_{n_j} T(n_j) + O(n \cdot k^2)$, where $n_j \le \frac{n}{2}$ denotes the number of vertices of the $j$-th subtree of $G-v$. Clearly, the depth of the recursion is $O(\log n)$ while the amount of work on each level of the recursion-tree is $O(n \cdot k^2)$.

Once the value of the optimal solution $\mu^*$ has been found, it is not too hard to see that the optimal solution itself can be reconstructed by proceeding in a bottom-up fashion, while keeping track of both the pebbles that move out of each subtree and the position where missing pebbles are to be placed.

To summarize, we have the following:

\[thm:con\_sum\_trees\] ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Sum}}}$ on trees can be solved in $O(n \cdot k^2 \log n)$ time.

Solving ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Num}}}$ on trees
----------------------------------------------------------------------------

The algorithm is similar to the one for ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Sum}}}$: we guess a vertex $r \in V(G)$ such that there exists an optimal solution that places a pebble on $r$, then we root the tree $G$ at $r$ (call $G_r$ the rooted tree) and we consider all the subtrees of $G_r$ in a bottom-up fashion.

Let $\varphi(u)=|\{ p \in P : \sigma(p)=u \}|$ be the number of pebbles whose initial position is the vertex $u \in V(G)$.

As before, when the subtree $T_u$ (rooted at the vertex $u$) of $G_r$ is examined, we consider an auxiliary problem where we want to place exactly $j \le k$ pebbles on the vertices of $T_u$ in order to satisfy the properties \[it:con\_P1\] and \[it:con\_P2\].

We will measure the cost of a solution for this auxiliary problem by examining the number of pebbles placed on each vertex of $T_u$. Removing pebbles from a vertex costs nothing, while placing a pebble on a vertex costs $1$ if it comes from a different vertex. A way to visualize this auxiliary problem is to imagine the tree $T_u$ where no pebbles have been placed and a pool of $j$ pebbles to be distributed on its vertices. Each vertex $v$ of $T_u$ can hold up to $\varphi(v)$ pebbles for free, while each additional pebble placed on $v$ increases the overall cost by $1$.

We will denote by ${\ensuremath{\texttt{Opt}}}[u,j]$ the cost of the optimal movement for this auxiliary problem. To solve the original problem we need to find a solution corresponding to ${\ensuremath{\texttt{Opt}}}[r,k]$. We now show how to combine these auxiliary problems.

If $u$ is a leaf of $G_r$ then we have: $${\ensuremath{\texttt{Opt}}}[u,j] =
        \begin{cases}
            0       & \mbox{if } j \le \varphi(u); \\
            j-\varphi(u)    & \mbox{if } j > \varphi(u).
        \end{cases}$$

Otherwise, if $u$ is not a leaf, we can either place some pebbles on $u$ and the others on the subtrees rooted at its children ($j \ge 1$), or place no pebble at all in the whole subtree rooted at $u$ ($j=0$). We call $z$ the number of pebbles that are to be placed on $u$.

If $j=0$ we have ${\ensuremath{\texttt{Opt}}}[u,j] = 0$, otherwise: $${\ensuremath{\texttt{Opt}}}[u,j] = \min_{1 \le z \le j}\left\{ \max \{z-\varphi(u), 0\} + \min_{\substack{0 \le j_1, \dots, j_{\ell} \le j-z \\ \sum_{i=1}^{\ell} j_i = j-z }} \left\{ \sum_{i=1}^{\ell} {\ensuremath{\texttt{Opt}}}[v_i, j_i] \right\} \right\}$$ where $v_1, \dots, v_\ell$ are the children of $u$ in $G_r$.

As before, using the already shown dynamic-programming approach to optimally distributing the pebbles on the subtrees, we can find the values of ${\ensuremath{\texttt{Opt}}}[u,j]$ for a fixed $j$ and all $v \in V$, in $O(n \cdot k)$ time. Therefore the time required to compute all ${\ensuremath{\texttt{Opt}}}$ values for a single root $r$ is $O(n \cdot k^2)$ and the measure of the best solution is found in ${\ensuremath{\texttt{Opt}}}[r, k]$. As for ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Sum}}}$, it is not necessary to run the algorithm for all roots $r \in V(G)$ but we can choose a centroid $v$ of $G$ as starting root and then proceed recursively on the trees of $G-v$.

To summarize, we have the following:

\[thm:con\_num\_trees\] ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Num}}}$ on trees can be solved in $O(n \cdot k^2 \log n)$ time.

Independency motion problems {#sec:ind}
============================

In this section we focus on independency motion problems. First, we give a better characterization of the hardness of ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ (depending on the input graph), and then we show some positive results for our considered variants on paths and trees. Since if $k \geq n$ there is no feasible solution, we will consider only instances where $k < n$.

Hardness of ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ on bipartite graphs
-----------------------------------------------------------------------------------------------------------------------------------------------------------

As we already pointed out, for independency problems on general graphs it is [$\textsf{\upshape NP}$]{}-hard even to find any feasible solution since it would require to find an independent set of size at least $k$. Nevertheless, one may wonder whether independency motion problems are tractable on instances on which a maximum independent set can be found in polynomial time. We provide a negative answer to this question, at least for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$, by showing the following

![Instance of ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ and of ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ corresponding to the formula $(\bar{x}_1 \vee \bar{x}_2 \vee x_3) \wedge (x_1 \vee x_2 \vee \bar{x}_3)$. Pebbles are placed on black vertices.[]{data-label="fig:mov_ind_max"}](Fig2.eps)

\[thm:ind\_max\_sum\_hard\_bipartite\] ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ are [$\textsf{\upshape NP}$]{}-hard on bipartite graphs.

We will show a polynomial reduction from $\textsc{3-Sat}$ to the decisional versions of ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$. Recall that $\textsc{3-Sat}$ is the problem of deciding whether a formula $f$ in conjunctive normal form with three literals per clause is satisfiable. Let $X = \{ x_1, \dots, x_\tau \}$ be the set containing the variables of $f$, and let $m$ be the number of clauses. We will denote the $i$-th literal of the $j$-th clause with $\ell^i_j$.

Given an instance $f$ for $\textsc{3-Sat}$ we construct an instance for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ and for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ in the following manner:

-   For each variable $x_i \in X$ create a star with $3$ leaves labelled $u_i, x_i, \bar{x}_i$ and label the internal node $v_i$. Place one pebble on $u_i$ and one on $v_i$.

-   For each clause $(\ell^1_j \vee \ell^2_j \vee \ell^3_j)$ create a star with $4$ leaves labelled $\ell^1_j, \ell^2_j, \ell^3_j, w_j$ and label the internal node $z_j$. Place one pebble on $w_j$ and one on $z_j$.

-   For each literal $\ell^i_j$ of $f$ let $x_s$ be the corresponding variable; then, if $\ell^i_j$ is asserted add an edge between the two nodes labelled $\ell^i_j$ and $\bar{x}_s$, otherwise add an edge between the two nodes labelled $\ell^i_j$ and $x_s$.

Let $G$ be the resulting graph, $P$ the set containing the $2 \cdot (\tau+m)$ placed pebbles, and $\sigma$ the function that maps each pebble to its starting position (see Figure \[fig:mov\_ind\_max\]). Notice that $G$ is bipartite as we can partition the vertices into two sets $A=\{v_i : 1 \le i \le \tau\} \cup \{ \ell^i_j : 1 \le i \le 3 \wedge 1 \le j \le m \} \cup \{ w_j : 1 \le j \le m \}$ and $B=V(G) \setminus A$ such that no edge of $G$ has both its endpoints in the same set.

We claim that there exists an assignment that satisfies $f$ if and only if the optimal solution $\mu$ for the instance of ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ (resp., ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$) has measure at most $1$ (resp., $\tau + m$).

Suppose the existence of an assignment $\theta^* : X \to \{ {\ensuremath{\texttt{True}}}, {\ensuremath{\texttt{False}}}\}$ that satisfies $f$. Then we move a pebble starting on vertex $v_i$ to the vertex labelled $x_i$ if $\theta^*(x_i)={\ensuremath{\texttt{True}}}$, or to the vertex labelled $\bar{x}_i$ if $\theta^*(x_i)={\ensuremath{\texttt{False}}}$. Moreover, for each clause $(\ell^1_j \vee \ell^2_j \vee \ell^3_j)$ of $f$ at least one literal $\ell^i_j$ must be true w.r.t. $\theta^*$. This implies that the vertex labelled $\ell^i_j$ is adjacent only to $z_j$ and to a vertex $x_s$ where no pebble has been placed. We then move the pebble initially placed on vertex $z_j$ to the vertex $\ell^i_j$.

The resulting configuration of pebbles is an independent set for $G$ and each pebble has been moved to a node adjacent to its starting position. This implies that the maximum movement is $1$ and that the overall distance travelled by pebbles is $\tau + m$.

Conversely, suppose the existence of an optimal solution $\mu^*$ for the instance of ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ (resp., ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$) that has measure equal to $1$ (resp., $\tau+m$). Notice that for every pebble $p$ initially placed on a vertex labelled $v_i$, $\mu^*(p) \in \{ x_i, \bar{x}_i \}$ must hold, otherwise either $\mu^*$ would be unfeasible or $c(\mu^*)$ would be greater than $1$ (resp., $\tau+m$, since $\tau+m$ pebbles need to be moved). Similarly for every pebble $p$ initially placed on a vertex labelled $z_j$, $\mu^*(p) \in \{ \ell^j_1, \ell^j_2, \ell^j_3 \}$ must hold.

We construct an assignment $\theta$ for the variables in the following manner: if there is a pebble on the vertex labelled $x_i$ we set $\theta(x_i)= \mathrm{{\ensuremath{\texttt{True}}}}$, otherwise there must be a pebble on $\bar{x}_i$ and we set $\theta(x_i) = {\ensuremath{\texttt{False}}}$.

We now show that $\theta$ is, indeed, an assignment that satisfies $f$. For each clause $(\ell^1_j \vee \ell^2_j \vee \ell^3_j)$ the pebble placed on $z_j$ has been moved to a vertex $\ell^i_j$ corresponding to one of the three literals. This implies that no pebble has been moved to the unique vertex in $\cup_{i=1}^t\{x_i, \bar{x}_i\}$ that is adjacent to vertex $\ell^i_j$. The above implies that the variable corresponding to literal $\ell^j_i$ has been set to the value that satisfies $\ell^j_i$ and thus the whole clause is satisfied.

Apparently, the above technique cannot be straightforwardly adapted to ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Num}}}$, and so we leave this as an interesting open problem.

Approximability of ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$
------------------------------------------------------------------------------

Actually, as shown in Theorem \[thm:ind\_max\_sum\_hard\_bipartite\], ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ is hard already when the cost of an optimal solution is 1. This immediately implies the following:

\[cor:ind\_max\_2-inapx\] ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on bipartite graphs is not approximable in polynomial time within a factor of $2-\epsilon$ for any positive $\epsilon$, unless ${\ensuremath{\textsf{\upshape P}}}={\ensuremath{\textsf{\upshape NP}}}$.

We now show that this bound is tight, by providing a polynomial-time solution, which is optimal unless an additive term of $1$, to ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on any class of graphs where a maximum independent set can be found in polynomial time, e.g., perfect graphs (which include bipartite graphs), interval graphs, and claw-free graphs.

Given a graph $H$ and a subset of vertices $A \subseteq V(H)$ we will denote the open neighbourhood of $A$ by $N_H(A)=\left\{ v \in V(H) : \exists u \in A \mbox{ s.t. } (u,v) \in E(H) \right\}$. Moreover we will denote the closed neighbourhood of $A$ by $N_H[A]=A \cup N_H(A)$.

Let $U^*$ be a maximum independent set of $G$, the following lemma holds:

\[lemma:independent\_set\_neighborhood\] For each independent set $U$ of $G$ it is true that $|U^* \cap N_G[U]| \ge |U|$.

By contradiction, let $|U^* \cap N_G[U]| < |U|$ then $U^\prime = \left( U^* \setminus N_G[U] \right) \cup U = \left( U^* \setminus \left( U^* \cap N_G[U] \right) \right) \cup U$ is an independent set of $G$ and $|U^\prime| > |U^*|$.

To prove the next lemma we use the following well known result:

\[thm:hall\_s\_matching\] Let $H=(V_1 \cup V_2, E)$ be a bipartite graph. There exists a matching of size $|V_1|$ on $H$ iff $|A| \le |N_H(A)|, \linebreak \forall A \subseteq V_1$.

\[lemma:injective\_function\] For each independent set $U$ of $G$, there exists an injective function $f : U \to U^*$ such that $d_G(u,f(u)) \le 1$.

Construct the bipartite graph $H=(U \cup U^*, E)$ where all vertices of $U$ are considered to be distinct from the ones in $U^*$ and $E=\{(u,v) \in U \times U^* : v \in N_G[\{u\}] \}$. Notice that, by construction, if two vertices $u,v$ are adjacent in $H$ either they are the same vertex or they are adjacent in $G$, i.e., $d_G(u,v)\le 1$.

Now, Lemma \[lemma:independent\_set\_neighborhood\] implies that, for every $A \subseteq U$, we have $|N(A)| = |U^* \cap N_G[A]| \ge |A|$. Hence, from Hall’s Matching Theorem, there is a matching of size $|U|$ on $H$ (and thus the function $f$ exists).

We are now ready to prove:

\[thm:mov\_ind\_max\_opt\_plus\_one\] There exists a polynomial-time algorithm for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ which, for every class of graphs where the maximum independent set can be found in polynomial time, computes a solution $\tilde{\mu}$ such that $c(\tilde{\mu}) \le c^* + 1$ where $c^*$ is the measure of an optimal solution.

The algorithm computes a maximum independent set $U^*$ of $G$ then, if $k > |U^*|$ it reports infeasibility, otherwise it optimally moves the pebbles towards (a subset of) the vertices of $U^*$. To do that, it proceeds as follows: for every value of $z$ from $0$ to $n-1$, it computes a solution $S_z$ for the maximum matching problem on the auxiliary bipartite graph $H=(A \cup U^*,E)$, where each vertex in $A$ is associated with a pebble, and $(p \in A,v \in U^*) \in E$ if and only if $d_G(\sigma(p), v) \le z$.

Let $\tilde{z}$ be the first value of $z$ such that $|S_z|=k$, i.e., all the pebbles have been matched. For every pebble $p \in P$ set $\tilde{\mu}(p)=v$, where $v$ is the only vertex such that $(p,v)\in S_{\tilde{z}}$, and return $\tilde{\mu}$. Clearly $c(\tilde{\mu})=\tilde{z}$. Let $\mu^*$ be an optimal solution to ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ and let $U=\mu^*[P]$. By Lemma \[lemma:injective\_function\] there exists an injective function $f$ that maps every vertex of the independent set $U$ to an adjacent vertex of $U^*$. Thus, for every $p \in P$ we have $d_G(\sigma(p), \mu^*(p)) + d_G(\mu^*(p), f(\mu^*(p))) \le c^* + 1$, and therefore there exists a way to place all the pebbles on vertices of $U^*$ while travelling a maximum distance of at most $c^*+1$. This implies $\tilde{z} \le c^*+1$.

Independency motion problems on trees and paths
-----------------------------------------------

Concerning independency motion problems on trees, we are able to devise two dynamic-programming algorithms for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ and ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Num}}}$, respectively. We note that it remains open to establish whether ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on trees can be solved in polynomial time. We will, however, devise an efficient algorithm for solving ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on paths. The details of these algorithm are presented in the following subsections.

### Solving ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ on trees

Our dynamic-programming algorithm relies on the property of optimal solutions shown by Lemma \[lemma:sum\_tree\_no\_crossing\] that is valid also for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$.

The algorithm first roots the tree $G$ at an arbitrary vertex $r \in V(G)$ to obtain the rooted tree $G_r$, then considers all the subtrees of $G_r$ in a bottom-up fashion.

Here, the auxiliary problem we consider when a subtree $T_u$ of $G$ rooted at vertex $u$ is examined is that of placing exactly $j \le k$ pebbles on the vertices of $T_u$ such that their final positions induce an independent set of $G$ (and each pebble is placed on different vertex). Remind that $\eta(u)$ denotes the number of pebbles placed on $V(T_u)$. As for the connectivity problems, if $j < \eta(u)$ we want to move the $\eta(u)-j$ exceeding pebbles to the parent of $u$ (and thus outside $T_u$). In a similar manner, if $j > \eta(u)$, then the $j-\eta(u)$ missing pebbles are to be moved into $T_u$ from the parent of $u$, where we assume they are initially placed.

We will denote by ${\ensuremath{\texttt{Opt}}}[u,j]$ the cost of the optimal movement for this auxiliary problem. Notice that, in ${\ensuremath{\texttt{Opt}}}[u,j]$, we are accounting for the cost of traversing all the edges of $T_u$ plus the edge from $u$ to its parent. To solve the original problem we need to find a solution corresponding to ${\ensuremath{\texttt{Opt}}}[r,k]$. Clearly as $k=\eta(r)$ we do not have exceeding or missing pebbles, in this case. We now show how to combine these auxiliary problems.

Let ${\ensuremath{\texttt{Opt}}}^+[u,j]$ (resp., ${\ensuremath{\texttt{Opt}}}^-[u,j]$) with $u \in V(G)$ and $0 \le j \le n$ be the value of an optimal solution to the auxiliary problem where exactly one pebble must be placed on $u$ (resp., no pebble can be placed on $u$). Notice that ${\ensuremath{\texttt{Opt}}}[u,j] = \min \{ {\ensuremath{\texttt{Opt}}}^+[u,j], {\ensuremath{\texttt{Opt}}}^-[u,j] \}$. We will say that infeasible solutions have cost $+\infty$.

If $u$ is a leaf we clearly have: $${\ensuremath{\texttt{Opt}}}^+[u,j] =
            \begin{cases}
                |\eta(u) - 1| & \mbox{if } j = 1; \\
                +\infty & \mbox{if } j=0 \mbox{ or } j \ge 2. \\
            \end{cases}         
    \quad \enskip       
        {\ensuremath{\texttt{Opt}}}^-[u,j] =
            \begin{cases}
                \eta(u) & \mbox{if } j = 0; \\
                +\infty & \mbox{if } j \ge 1.
            \end{cases}$$

If $u$ is not a leaf then we can either place a pebble on $u$ or not. If we do place it, the corresponding optimal value is: $${\ensuremath{\texttt{Opt}}}^+[u,j] =
        \begin{cases}
            +\infty & \mbox{if } j=0; \\
            |\eta(u) - j| + {\displaystyle \min_{\substack{0 \le j_1, \dots, j_{\ell} < j \\ \sum_{i=1}^{\ell} j_i = j-1}}} \left\{ \sum_{i=1}^{\ell} {\ensuremath{\texttt{Opt}}}^-[v_i, j_i] \right\} & \mbox{if } j \ge 1,
        \end{cases}$$ where $v_1, \dots, v_\ell$ is the set of children of $u$ in $G_r$. If $j$ is at least $1$ we place a pebble on $u$ and then consider all the possible ways of placing a total of $j-1$ pebbles on the subtrees rooted at the children of $u$, but not on the children themselves.

If we do not place a pebble on $u$, then the optimal value is: $${\ensuremath{\texttt{Opt}}}^-[u,j] = |\eta(u) - j| + {\displaystyle \min_{\substack{0 \le j_1, \dots, j_{\ell} \le j \\ \sum_{i=1}^{\ell} j_i = j }}} \left\{ \sum_{i=1}^{\ell} {\ensuremath{\texttt{Opt}}}[v_i, j_i] \right\}.$$

This corresponds to the optimal way of placing $j$ pebbles on the subtrees rooted at the children of $u$.

As we have previously shown, the optimal assignment to $j_1, \dots, j_{\ell}$ can be found in $O(\ell \cdot k)$ time by using dynamic programming. The value of the optimal solution is stored in ${\ensuremath{\texttt{Opt}}}[r, k]$ and the solution itself can be reconstructed by proceeding backwards as shown in Section \[sec:con\_sum\_trees\] for ${\ensuremath{\textsc{Con}}}$-${\ensuremath{\textsc{Sum}}}$.

As we can compute the values ${\ensuremath{\texttt{Opt}}}[u,j]$, for a fixed $j$ and all $v \in V$, in $O(n \cdot k)$ time (the $\ell$-values sum up to $n-1$), the total time required by the algorithm is $O(n \cdot k^2)$.

The above discussion, immediately leads to the following:

\[thm:ind\_sum\_trees\] ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ on trees can be solved in ${\ensuremath{O}}(n \cdot k^2)$ time.

### Solving ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Num}}}$ on trees

The algorithm is similar to the one for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$: we root the tree $G$ at an arbitrary vertex $r \in V(G)$ to obtain the rooted tree $G_r$, then we consider all the subtrees of $G_r$ in a bottom-up fashion.

Let $\gamma(u)$ be $1$ if at least one pebble is initially placed on the vertex $u \in V(G)$, and $0$ otherwise. As before, when the subtree $T_u$, rooted at the vertex $u$, of $G_r$ is examined, we consider an auxiliary problem where we want to place exactly $j \le k$ pebbles on the vertices of $T_u$ such that their final positions induce an independent set of $G$ (and each pebble is placed on a different vertex).

We will measure the cost of a solution for this auxiliary problem by examining the number of pebbles placed on each vertex of $T_u$. Removing pebbles from a vertex costs nothing, while placing a pebble on a vertex costs $1$ if it comes from a different vertex. A way to visualize this auxiliary problem is to imagine the tree $T_u$ where no pebbles have been placed, and a pool of $j$ pebbles to be distributed on its vertices. If a vertex $v$ is such that $\gamma(v)=1$ then it can hold a single pebble for free, otherwise placing a pebble on $v$ will increase the overall cost by $1$.

We will denote by ${\ensuremath{\texttt{Opt}}}[u,j]$ the cost of the optimal movement for this auxiliary problem. To solve the original problem we need to find a solution corresponding to ${\ensuremath{\texttt{Opt}}}[r,k]$. We now show how to combine these auxiliary problems.

Let ${\ensuremath{\texttt{Opt}}}^+[u,j]$ (resp., ${\ensuremath{\texttt{Opt}}}^-[u,j]$) with $u \in V(G)$ and $0 \le j \le n$ be the value of an optimal solution to the auxiliary problem where exactly one pebble must be placed on $u$ (resp., no pebbles can be placed on $u$). Notice that ${\ensuremath{\texttt{Opt}}}[u,j] = \min \{ {\ensuremath{\texttt{Opt}}}^+[u,j], {\ensuremath{\texttt{Opt}}}^-[u,j] \}$. We will say that infeasible solutions have cost $+\infty$.

If $u$ is a leaf of $G_r$ then we have: $${\ensuremath{\texttt{Opt}}}^+[u,j] =
        \begin{cases}
            +\infty & \mbox{if } j=0 \mbox{ or } j \ge 2; \\
            1-\gamma(u) & \mbox{if } j=1.
        \end{cases} \quad \quad
        {\ensuremath{\texttt{Opt}}}^-[u,j] =
        \begin{cases}
            0       & \mbox{if } j=0; \\
            +\infty & \mbox{if } j \ge 1.
        \end{cases}$$

If $u$ is not a leaf then, with a reasoning similar to that we did for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Sum}}}$ we have: $${\ensuremath{\texttt{Opt}}}^+[u,j] =
        \begin{cases}
            +\infty & \mbox{if } j=0; \\
            1-\gamma(u) + {\displaystyle \min_{\substack{0 \le j_1, \dots, j_{\ell} < j \\ \sum_{i=1}^{\ell} j_i = j-1}}} \left\{ \sum_{i=1}^{\ell} {\ensuremath{\texttt{Opt}}}^-[v_i, j_i] \right\} & \mbox{if } j \ge 1,
        \end{cases}$$ and $${\ensuremath{\texttt{Opt}}}^-[u,j] =
         \min_{ \substack{0 \le j_1, \dots, j_{\ell} \le j \\ \sum_{i=1}^{\ell} j_i = j} } \left\{ \sum_{i=1}^{\ell} {\ensuremath{\texttt{Opt}}}[v_i, j_i] \right\},$$ where $v_1, \dots, v_{\ell}$ are the children of $u$ in $G_r$.

Again, the optimal assignment to $j_1, \dots, j_\ell$ can be found in $O(\ell \cdot k)$ time by using dynamic programming. The value of the optimal solution is stored in ${\ensuremath{\texttt{Opt}}}[r, k]$ and the solution itself can be reconstructed by proceeding backwards. As we can compute the values ${\ensuremath{\texttt{Opt}}}[u,j]$, for a fixed $j$ and all $v \in V$, in $O(n \cdot k)$ time (the $\ell$-values sum up to $n-1$), the total time required by the algorithm is $O(n \cdot k^2)$.

The above discussion immediately leads to the following:

\[thm:ind\_num\_trees\] ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Num}}}$ on trees can be solved in ${\ensuremath{O}}(n \cdot k^2)$ time.

### Solving ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on paths

In this section we concentrate on ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$, and we devise an efficient algorithm for solving ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on the special case where $G$ is a path. We start by proving the following:

\[lemma:swap\] Let $s_1, s_2, e_1, e_2 \in \mathbb{N}$ where $s_1 \le s_2$ and $e_2 \le e_1$, we have $\max\left\{ | s_1 - e_1|, |s_2 - e_2| \right\} \ge \max\left\{ | s_1 - e_2|, |s_2 - e_1| \right\}$.

Suppose that $| s_1 - e_2| \ge |s_2 - e_1|$. If $s_1 \ge e_2$ then $|s_2 - e_2| \ge |s_1 - e_2|$, else if $s_1 < e_2$ then $|s_1 - e_1| = e_1 - s_1 \ge  e_2 -s_1 = |s_1 - e_2|$.

In a similar manner suppose $|s_1 - e_2| \le |s_2 - e_1|$. If $s_2 \ge e_1$ then $|s_2 - e_2| \ge |s_2 - e_1|$, else if $s_2 < e_1$ then $|s_1 - e_1| = e_1 - s_1 \ge e_1 - s_2 = |s_2 - e_1|$.

Let $r$ be any endpoint of $G$, with a little abuse of notation we will identify the vertices of $G$ by their distance from $r$: the vertex $i$ with $0 \le i < n$ will be the unique vertex $u$ such that $d_G(r, u)=i$.

Let $p_1, \dots, p_k$ be an ordering of the pebbles such that $\sigma(p_i) \le \sigma(p_{i+1})$ for $i=1,\dots,k-1$. The following lemma shows that there exists an optimal solution where the ordering of pebbles is preserved, i.e., no edge of $G$ is traversed by two pebbles going in opposite directions.[^4]

\[lemma:no\_crossing\] If there exists a feasible solution $\mu$ for ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on paths then there also exists a solution $\mu^\prime$ such that $\mu^\prime(p_i) < \mu^\prime(p_{i+1})$ for every $i=1,\dots,k-1$ and $c(\mu^\prime) \le c(\mu)$.

Let $\mu$ be a feasible solution. We will show that whenever there are two pebbles $p_i$ and $p_{i+1}$ such that $\mu(p_i) > \mu(p_{i+1})$, they can be swapped without increasing the cost of $\mu$ to obtain another feasible solution.[^5] If needed, the procedure can be repeated until all the pebbles are placed in the right order.

In order to prove the above, consider a new solution $\mu^\prime$ where $\mu^\prime(p_i)=\mu(p_{i+1})$, $\mu^\prime(p_{i+1})=\mu(p_i)$, and $\mu^\prime(p_j) = \mu(p_j)$ for every $j \not\in \{i,i+1\}$. Clearly $\mu^\prime$ is feasible (as we only swapped two pebbles) and requires at most the same maximum movement as $\mu$, because: $$\begin{gathered}
            \max\left\{ d_G(\sigma(p_i), \mu(p_i)), d_G(\sigma(p_{i+1}), \mu(p_{i+1})) \right\} \ge \\
            \max\left\{ d_G(\sigma(p_i), \mu(p_{i+1})), d_G(\sigma(p_{i+1}), \mu(p_{i})) \right\},
        \end{gathered}$$ where every distance $d_G(u,v)$ between two vertices $u$ and $v$ can be rewritten as $|u - v|$ and Lemma \[lemma:swap\] holds.

The algorithm takes as input an instance of ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ plus a non-negative integer $z$ and exploits the previous property to compute a solution of cost at most $z$, if it exists. The idea is simple: the pebbles are moved towards the endpoint $r$ of the path as most as possible while preserving the feasibility of the solution and the constraint on the cost. The pseudocode is given below.

$p_1, \dots, p_k \gets$ pebbles sorted by distance from $r$

$next \gets 0$ $\mu$

\[lemma:alg1\_correctness\] Algorithm \[alg:IndMax\] correctly returns a solution with maximum movement at most $z$, if such a solution exists, or reports infeasibility if there is no such solution.

First notice that all solutions returned by the algorithm are feasible as no two pebbles can be placed on adjacent vertices and, by construction, no pebble travels a distance greater than $z$. This implies that if there is not a feasible solution, the algorithm correctly reports infeasibility.

Now we will prove that the algorithm correctly computes a solution when this exists. Let $\mu^*$ be a solution with maximum movement at most $z$ that preserves the ordering of the pebbles (by Lemma \[lemma:no\_crossing\] such a solution always exists). We will prove by induction that at the end of the $j$-th loop the first $j$ pebbles are correctly placed (they are on an independent set), and that for the $j$-th pebble $\mu(p_j) \le \mu^*(p_j)$ holds.

Base case: the first pebble is placed on the first reachable node from $r$, thus $\mu(p_1) \le \mu^*(p_1)$ must hold.

Inductive step: suppose that the property is true for the first $j \ge 1$ pebbles, we will prove that it is also true also for the $(j+1)$-th pebble. If the pebble $p_{j+1}$ is placed on vertex $\sigma(p_{j+1})-z$ then the property holds, since this is the vertex with the smallest distance from $r$ that is reachable by $p_{j+1}$. Otherwise $\mu(p_{j+1}) = \mu(p_j)+2$, and we have $\mu^*(p_{j+1}) \ge \mu^*(p_j) + 2 \ge \mu(p_j) + 2=\mu(p_{j+1})$.

We are ready to give the following:

\[thm:ind\_max\_paths\] ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on paths can be solved in ${\ensuremath{O}}(n + k \log n)$ time.

From Lemma \[lemma:alg1\_correctness\] it follows that ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on paths can be solved as follows: if $k > n$ then there is no solution, otherwise we can perform a binary search using Algorithm \[alg:IndMax\] to find the optimal value of $k$ (or report infeasibility).

As far as the time complexity is concerned, each invocation of the algorithm requires time $O(k)$ and at most $O(\log n)$ invocations are required. For Algorithm \[alg:IndMax\] to work, vertices and pebbles must be sorted w.r.t. their distance from $r$, and this needs to be done only once and requires $O(n + k)$ time. The whole procedure then takes $O(n + k \log n)$ time.

Clique motion problems {#sec:clique}
======================

In this section we prove that the problems ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Max}}}$, ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$, and ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ are [$\textsf{\upshape NP}$]{}-hard. Then, we give a tight approximation algorithm for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Max}}}$ that computes a solution that costs at most one more than the optimal solution. As of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$ and ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$, we show that the problems are not approximable within any factor smaller than $10\sqrt{5}-21$, unless ${\ensuremath{\textsf{\upshape P}}}={\ensuremath{\textsf{\upshape NP}}}$, and we devise two $2$-approximation algorithms.

Actually, we will show that any approximation for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$ or ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ implies an approximation with the same ratio for the *minimum vertex cover* problem, which is known to be not approximable under $10\sqrt{5}-21$, unless ${\ensuremath{\textsf{\upshape P}}}={\ensuremath{\textsf{\upshape NP}}}$ [@dinur2005hardness]. Moreover, if the unique game conjecture [@khot2002power] is true, then both approximation algorithms are tight as the corresponding problems are not approximable within any constant factor better than $2$ [@khot2008vertex].

Finally, we show that for classes of graphs where we can find a *maximum-weight clique* in polynomial time, we can also solve ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ in polynomial time.

Approximability of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Max}}}$
---------------------------------------------------------------------------------

We prove the following:

${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Max}}}$ is [$\textsf{\upshape NP}$]{}-hard.

We show a reduction from the problem of determining if there exists a *dominating clique* in a graph $H$, which is known to be [$\textsf{\upshape NP}$]{}-complete [@haynes1998domination]. A dominating clique is a subset of vertices $C \subseteq V(H)$ such that $C$ is both a clique and a dominating set for $H$.

We construct an instance of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Max}}}$ by setting $G=H$ and placing a pebble on each vertex of $G$. We claim that there exists a dominating clique in $H$ if and only if the optimal solution for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Max}}}$ has measure $c^*$ at most $1$.

Suppose that there exists a dominating clique $C$ in $H$. By definition, $C$ is also a dominating set of $G$. We define $\mu$ so that every pebble initially placed on a vertex $u \not\in C$ is moved to a vertex $v \in C$ such that $(u,v) \in E(G)$ (notice that such a vertex always exists). After their movement the pebbles are placed on a clique of $G$ and each pebble has travelled a distance of at most $1$.

Now suppose that there exists a solution $\mu$ for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Max}}}$ such that $c(\mu) \le 1$. Clearly $\mu[P]$ is a clique, and it is also a dominating set, since for each vertex $u \not\in \mu[P]$, there exists a vertex $v \in \mu[P]$ such that $(u,v) \in G$.

On the positive side, we have:

It is possible to compute a solution $\tilde{\mu}$ for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Max}}}$ such that $c(\tilde{\mu}) \le c^* + 1$ in polynomial time, where $c^*$ is the measure of an optimal solution.

Consider the following algorithm: for each vertex $u \in V(G)$ construct a solution $\mu_u$ that moves all the pebbles to $u$ (i.e., set $\mu_u(p)=u, \; \forall p \in P$) and compute $c(\mu)$. Among the $n$ possible solutions choose the one of minimum cost and call it $\tilde{\mu}$.

Now, let $\mu^*$ be an optimal solution and recall that, by definition, $c(\mu^*) = \max_{p \in P} \left\{ d_G(\sigma(p), \mu^*(p))  \right\}$. Let $C=\mu^*[P]$ be the clique where pebbles have been placed by $\mu^*$, and notice that when the above algorithm considers a node $u \in C$ we have: $ d_G(\sigma(p), \mu_u(p)) \le d_G(\sigma(p), \mu^*(p)) + 1 \; \forall p \in P
    $, thus $c(\tilde{\mu}) \le c(\mu_u) \le c(\mu^*)+1$. The claim follows.

Approximability of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$
---------------------------------------------------------------------------------

We prove the following:

\[thm:2-apx-mov-clique-num\] ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ is $2$-approximable and is not approximable within any constant factor smaller than $10\sqrt{5}-21$, unless ${\ensuremath{\textsf{\upshape P}}}={\ensuremath{\textsf{\upshape NP}}}$.

Let $\langle G, P, \sigma \rangle$ be an instance of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ and let $\varphi(u) = |\{p \in P : \sigma(p)=u \}|$ be the number of pebbles that are initially placed on vertex $u \in V$. Let us assume that $\varphi(u) \le 1$ for every $u \in V$, i.e., no two pebbles are placed on the same vertex. We will show later that this assumption is not restrictive. Call $H$ the graph induced by the vertices $u$ with $\varphi(u)=1$. Let $\bar{H}$ be the complement graph of $H$ w.r.t. the edge set, that is the graph such that $V(\bar{H})=V(H)$ and $E(\bar{H}) = \{ (u,v) : u,v \in V(H) \wedge u \not= v \wedge (u,v) \not\in E(H) \}$. We will show that there exists a vertex cover $\mathcal{C}$ for $\bar{H}$ if and only if there exists a solution for the instance $\langle G, P, \sigma \rangle$ of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ of cost $|\mathcal{C}|$.

Let $\mathcal{C}$ be a vertex cover for $\bar{H}$, this implies that $Q=V(H)-\mathcal{C}$ is an independent set for $\bar{H}$, and therefore a clique for $H$ and $G$. We construct a solution $\mu$ for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ by moving the $|\mathcal{C}|$ pebbles that are not yet placed on vertices in $Q$ to one of such vertices. Now let $\mu$ be a solution for the instance $\langle G, P, \sigma \rangle$ of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ and let $Q=\{u \in V(H) : \exists p \in P \mbox{ s.t. } \sigma(p)=\mu(p)=u\}$. Notice that the cost of $\mu$ is exactly $k-|Q|=|V(H)-Q|$. Clearly $Q \subseteq \mu[P]$ is a clique for $G$ and $H$, therefore it is also an independent set for $\bar{H}$. This implies that $\mathcal{C}=V(H)-Q$ is a vertex cover for $\bar{H}$.

From the above it follows that the cost of an optimal solution is equal to the size of the minimum vertex cover for $\bar{H}$. To approximate ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ we construct the graph $\bar{H}$, we compute a $2$-approximate minimum vertex cover $\mathcal{\tilde{C}}$, and then we reconstruct the solution $\mu$ as shown.

If the previous assumption is not met, i.e., there exists at least a vertex on which two or more pebbles are placed by $\sigma$, a slight modification to the instance is needed before we can apply the previous approach. We modify the graph $G$ by replacing each vertex $u$ such that $\varphi(u)>1$ with a clique of size $\varphi(u)$. Each edge $e$ incident to $u$ is replaced by $\varphi(u)$ edges connecting every vertex of the clique to the other endpoint of $e$. Then, we modify the function $\sigma$ so that the $\varphi(u)$ pebbles that were placed on $u$ are assigned to each of the $\varphi(u)$ vertices of the corresponding clique. After the modifications, the cost of an optimal solution has not changed, moreover every solution for the modified instance can be easily reconverted to a solution for the original instance without increasing its cost. Hence, we have designed a $2$-approximation algorithm for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$.

Concerning the inapproximability result, we prove it by contradiction: we show that if there exists an algorithm that approximates ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ with a ratio better than $10\sqrt{5}-21$, then this would allow to approximate minimum vertex cover with the same approximation ratio. Indeed, let $\bar{H}$ be the instance of minimum vertex cover. Now, add an isolated vertex $u$ and call $G$ the complement of such a graph w.r.t. the edge set. Then, let $P=[|V(G)|-1]$, and let $\sigma$ be a function that places a single pebble on each vertex of $G$ except $u$. We can now compute an approximate solution for the instance $\langle G, P, \sigma \rangle$ of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ and reconstruct a solution with the same cost for minimum vertex cover, as shown before.[^6]

We close this section by proving that ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ can be solved in polynomial time whenever we are able to solve the maximum-weight clique problem on a weighted variant of $G$. We remark that this is known to be the case of several classes of graphs, including perfect graphs. We refer the interested reader to [@bomze1999maximum] for a survey.

An exact solution to ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ can be found in polynomial time on every class of graphs where a maximum-weight clique can be found in polynomial time.

For every $v \in V$ let $\varphi(v)$ be the number of pebbles starting on vertex $v$, i.e., $\varphi(v)=|\{p \in P : \sigma(p)=v\}|$.

We consider a graph $H=(V,E)$ that is a copy of $G$ where each vertex $v \in V$ has a weight $\varphi(v)$. Then, we compute a maximum-weight clique $Q$ of $H$ and construct a solution $\mu$ for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ by moving every pebble starting on a vertex in $V \setminus Q$ to an arbitrary vertex of $Q$.[^7] It is now easy to see that this is an optimal solution, since for every other solution $\mu^\prime$, we have: $$c(\mu^\prime) = \sum_{v \not\in \mu^\prime[P]} \varphi(v) =
            k-\sum_{v \in \mu^\prime[P]} \varphi(v) \ge k-\sum_{v \in Q} \varphi(v) =
            \sum_{v \not\in \mu[P]} \varphi(v) = c(\mu).$$

Approximability of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$
---------------------------------------------------------------------------------

We prove the following:

${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$ is $2$-approximable and is not approximable within any constant factor better than $10\sqrt{5}-21$, unless ${\ensuremath{\textsf{\upshape P}}}={\ensuremath{\textsf{\upshape NP}}}$.

Let $\mu^*$ be an optimal solution to ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$. If $\mu^*$ moves all the pebbles (i.e., $\sigma(p) \not= \mu^*(p), \; \forall p \in P$) then we can compute a $2$-approximate solution $\tilde{\mu}$ by guessing a vertex $u \in \mu^*[P]$ and moving all the pebbles to $u$ (i.e., setting $\tilde{\mu}(p)=u, \; \forall p \in P$). Indeed, we have: $$\frac{c(\tilde{\mu})}{c(\mu^*)} = \frac{\sum_{p \in P}d_G(\sigma(p), \tilde{\mu}(p))}{\sum_{p \in P}d_G(\sigma(p), \mu^*(p))} \le \frac{|P| + \sum_{p \in P}d_G(\sigma(p), \mu^*(p))}{\sum_{p \in P}d_G(\sigma(p), \mu^*(p))} \le 2$$ where we used the fact that $d_G(\sigma(p), \tilde{\mu}(p)) \le d_G(\sigma(p), \mu^*(p))+1$, and that $d_G(\sigma(p), \mu^*(p)) \ge 1$, for every pebble $p \in P$.

On the other hand, if there exists at least one pebble $p^\prime \in P$ such that $\sigma(p^\prime)=\mu^*(p^\prime)$, then we guess its starting vertex $u=\sigma(p^\prime)$. We call $P_0$ the set of pebbles whose starting vertex is $u$, $P_1$ the set of pebbles whose starting vertex is adjacent to $u$, and $P_{2}$ the set of pebbles that are initially placed on a vertex at distance $2$ or more from $u$. We then set $\tilde{\mu}(p)=u$ if $p \in P_0$ or $p \in P_{2}$. With a reasoning similar to the one of the previous case we can show that: $$\sum_{p \in P_{2}} d_G(\sigma(p), \tilde{\mu}(p))  \le |P_{2}| + \sum_{p \in P_{2}} d_G(\sigma(p), \mu^*(p)) \le 2 \sum_{p \in P_{2}} d_G(\sigma(p), \mu^*(p)) \mbox{.}$$ Concerning $P_1$, assume $P_1\not=\emptyset$, and so we need to compute $\tilde{\mu}$ for the pebbles in $P_1$. To do that, consider the instance $\langle H, P_1, \sigma \rangle$ of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$ where $H$ is the subgraph of $G$ induced by the vertices initially occupied by pebbles in $P_1 \cup \{ p^\prime \}$, and compute a $2$-approximate solution $\mu^\prime$ as shown in Theorem \[thm:2-apx-mov-clique-num\]. Set $\tilde{\mu}(p)=\sigma(p)$ for every pebble $p \in P_1$ such that $\mu^\prime(p)=\sigma(p)$, and set $\tilde{\mu}(p)=u$ for the remaining pebbles in $P_1$.

Clearly $\tilde{\mu}[P]$ is a clique for $G$ as the vertices in $\mu^\prime[P_1]$ are a clique for $G$, $u$ is adjacent to every vertex in $\mu^\prime[P_1]$, and $\tilde{\mu}[P] \subseteq \mu^\prime[P_1] \cup \{ u \}$.

Notice that the cost of moving the pebbles in $P_1$ w.r.t. $\mu^*$ is greater than or equal to the cost of the optimal solution for the instance $\langle H, P_1, \sigma \rangle$ of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Num}}}$. Moreover, the cost of moving the pebbles in $P_1$ w.r.t. $\tilde{\mu}$ is equal to the cost of $\mu^\prime$. From the above it follows that: $$\sum_{p \in P_1} d_G(\sigma(p), \tilde{\mu}(p)) \le 2 \sum_{p \in P_1} d_G(\sigma(p), \mu^*(p)) \mbox{.}$$

Therefore, the overall cost of this approximated solution is: $$c(\tilde{\mu}) \le 2 \sum_{p \in P_1} d_G(\sigma(p), \mu^*(p)) + 2 \sum_{p \in P_{2}} d_G(\sigma(p), \mu^*(p)) \le 2 \,c(\mu^*) \mbox{.}$$

Concerning the inapproximability result, take a graph $H=(V, E)$ and construct the graph $G$ by complementing $H$ w.r.t. the edge set and adding an additional vertex $v_0$ adjacent to every other vertex. Let $P=[|V(H)|]$ and let $\sigma$ be a function that places one pebble on each vertex of $G$ except $v_0$. We will show that, given any solution for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$, it is possible to construct a vertex cover of $H$ having the same cost, and vice versa. This implies that any approximation algorithm for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$ converts into an approximation algorithm for minimum vertex cover with the same approximation ratio, therefore no approximation algorithm with an approximation ratio less than $10\sqrt{5}-21$ can exist for ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$ [@dinur2005hardness], unless ${\ensuremath{\textsf{\upshape P}}}={\ensuremath{\textsf{\upshape NP}}}$.

Let $\mathcal{C}$ be a vertex cover for $H$, then $V(H)-\mathcal{C}$ is an independent set for $H$ and a clique for $G$. The solution that moves all the pebble of $\mathcal{C}$ to $v_0$ and leaves the others on their starting position is feasible and has a cost of $\mathcal{C}$.

Now let $\mu$ be a solution for the instance of ${\ensuremath{\textsc{Clique}}}$-${\ensuremath{\textsc{Sum}}}$. We modify $\mu$ in such a way that every pebble that moves at least by $1$ is now moving to $v_0$. This modification cannot increase the cost of $\mu$. Then, let $Q= \mu[P] \setminus \{ v_0 \}$, and let $\mathcal{C}=V(H) \setminus Q$. The cost of $\mu$ is $|V(H)|-|Q|=|\mathcal{C}|$, and $Q \subseteq \mu[P]$ is a clique for $G$. Therefore $Q$ is also an independent set for $H$, and $\mathcal{C}$ is a vertex cover for $H$.

${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$ motion problems {#sec:stcut}
===============================================================

In this section we discuss (in)approximability results for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$. Among the others, we provide an essentially tight approximation algorithm for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$. Regarding ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Num}}}$, establishing its tractability remains open, but we will show that approximating such a problem can be useful to approximate ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$, as well. We start by proving the following:

![Instance of ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ corresponding to the formula $(x_1 \vee x_2 \vee x_3) \wedge (\bar{x}_1 \vee \bar{x}_2 \vee x_3)$. Pebbles are placed on black vertices. All the edges not incident to a black vertex represent paths of length $h$ between their endpoints.[]{data-label="fig:cut_max_hard"}](Fig3.eps)

\[thm:cut\_max\_sum\_hard\_bipartite\] ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$ are [$\textsf{\upshape NP}$]{}-hard even if $G$ is a bipartite graph.

We will show a reduction from the decision version of $\textsc{3-Sat}$. Let $X=\{x_1, \dots, x_\tau\}$ be the set of variables of the given formula $f$, and let $m$ be the number of clauses. Start with an empty graph $G$ and a set $P$ of $\tau + 2m$ pebbles, then construct an instance for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$ as follows (see Figure \[fig:cut\_max\_hard\] for an example):

-   Add the two vertices $s$ and $t$.

-   For each variable $x_i \in X$ add a path of three vertices to $G$. Label the middle node $u_i$ and the two endpoints $x_i$ and $\bar{x}_i$, respectively. Place a pebble on $u_i$.

-   For each clause $(\ell^1_j \vee \ell^2_j \vee \ell^3_j)$ create a path of five vertices labelled, from one endpoint to another, $\ell^j_1, v_j, \ell^j_2, v_j^\prime, \ell^j_3$. Place a pebble on $v_j$ and one on $v_j^\prime$.

-   For each literal $\ell^i_j$ of $f$, let $x_s$ be the corresponding variable. If $\ell^i_j$ is asserted add a new “long” path of length $h> k = t + 2 m$ between the vertices labelled $\ell^i_j$ and $x_s$ (so that $d_G(\ell^i_j,x_s)=h$). Otherwise add a new “long” path between the vertices labelled $\ell^i_j$ and $\bar{x}_s$.

-   Connect $s$ to every vertex $x_i$ and to every vertex $\bar{x}_i$ with a new “long” path of length $h$.

-   Connect $t$ to every vertex $\ell^j_i$ with a new “long” path of length $h$.

Notice that $G$ is bipartite as every cycle in $G$ must pass trough an even number of long paths (paths of length $h$) and an even number of other edges.

We will show that there exists a truth assignment satisfying $f$ if and only if an optimal solution for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ (resp., ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$) has cost at most $1$ (resp., $k$).

Suppose that there exists a truth assignment $\theta^* : X \to \{ {\ensuremath{\texttt{True}}},{\ensuremath{\texttt{False}}}\}$ that satisfies $f$. Then, for each $x_i \in X$ we move the pebble placed on $u_i$ to $x_i$ if $\theta^*(x_i)={\ensuremath{\texttt{True}}}$, and to $\bar{x}_i$ if $\theta^*(x_i)={\ensuremath{\texttt{False}}}$. Moreover, for each clause $(\ell^1_j \vee \ell^2_j \vee \ell^3_j)$ there are at most $2$ literals whose truth values are false w.r.t. $\theta^*$. We move one or two of the pebbles placed on $v_j$ and $v^\prime_j$ to the nodes of $G$ corresponding to the those literals.

Notice that in this way each pebble travels at most a distance of $1$ (so the sum of the distances is at most $k$). To prove that the new positions of the pebbles induce an *s-t*-cut in $G$, consider any path $\pi(s,t)$ in $G$ between $s$ and $t$. We will show that $\pi(s,t)$ has been “blocked”, i.e, there exists at least one pebble that has been moved on some vertex of $\pi(s,t)$.

The path $\pi(s,t)$ must contain (as subpath) at least one path of length $h$ that connects a vertex $x \in \{x_i, \bar{x}_i\}$ for (some $i$) to a vertex $\ell \in \{\ell^1_j, \ell^2_j, \ell^3_j\}$ (for some $j$). If a pebble has been placed on $x$ then $\pi(s,t)$ is blocked. Otherwise the literal represented by $\ell$ must be false and, by construction, a pebble has been placed on $\ell$.

Now suppose that an optimal solution for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ (resp., ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$) has cost at most $1$ (resp., $k$). Notice that every pebble must have travelled a distance of at most $1$. This is trivial for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$, while for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$ it suffices to note that placing a pebble on an internal vertex of the paths of length $h$ blocks at most the same set of paths that are blocked by placing it on one of the endpoints. Moreover no pebble can traverse a whole path as $h > k$.

We define $\theta(x_i)={\ensuremath{\texttt{True}}}$ if a pebble has been placed on $x_i$, and $\theta(x_i)={\ensuremath{\texttt{False}}}$ otherwise. For each clause $(\ell^1_j \vee \ell^2_j \vee \ell^3_j)$ there exists at least one vertex $\ell \in \{\ell^1_j, \ell^2_j, \ell^3_j \}$ such that no pebble has been moved to $\ell$. Let $x_i$ be the variable associated with $\ell_i$, and let $x$ be the vertex labelled $x_i$ if $\ell = x_i$, or the vertex labelled $\bar{x}_i$ if $\ell = \bar{x}_i$. The pebble placed on $u_i$ must have been moved to $x$, otherwise there would exist a path from $s$ to $t$ passing through $x$ and $\ell$, and therefore the clause is satisfied.

We now show that ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$ are actually very hard to approximate:

${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ and ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$ are not approximable within a factor of $n^{1-\epsilon}$ for every $\epsilon>0$, unless ${\ensuremath{\textsf{\upshape P}}}={\ensuremath{\textsf{\upshape NP}}}$. This also holds for bipartite graphs.

As shown in the proof of Theorem \[thm:cut\_max\_sum\_hard\_bipartite\], it is possible to construct instances of ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ (and ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$) such that the optimal solution has measure at most $1$ (resp., $k=\tau + 2m$) if and only if a boolean formula in conjunctive normal form with three literals per clause, $\tau$ variables, and $m$ clauses is satisfiable. Moreover, any solution with cost $z$ such that $\tau+2m < z < h$ (recall that $h$ is the length of the “long” paths) can be easily transformed into a solution of cost at most $\tau + 2m$ by moving every pebble $p$ that has been placed on one long path to an appropriate endpoint (i.e., the one adjacent to $\sigma(p)$). This implies that if $f$ is satisfiable, the measure $z^*$ of an optimal solution is at most $k$ for both the problems, while if $f$ is not satisfiable, $z^*$ is at least $h$.

Then, given a formula $f$, construct an instance for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ (and ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$) as in the proof of Theorem \[thm:cut\_max\_sum\_hard\_bipartite\], and suppose that there exists a polynomial-time algorithm that approximates the optimal solution within a factor of $n^{1-\epsilon}$, for some positive $\epsilon \le 1$. Let $\tilde{c}$ be the measure of such an approximate solution. Observe that it is possible to upper bound the number of vertices $n$ of the instance with the quantity $2 + 3\tau + 5m + 2\tau h + 6mh \le 11h(\tau+m) \le 11hk$.

If $f$ is satisfiable, we have $\tilde{c} \le k n^{1-\epsilon}$, while if $f$ is not satisfiable we have $\tilde{c} \ge h$. If $k n^{1-\epsilon} < h$ holds then it is possible to decide $\textsc{3-Sat}$ by running the approximation algorithm and looking the measure of the approximate solution. This can be guaranteed by choosing $h > (11k)^{2/\epsilon}$, as we have $h^\epsilon > 11 k^2 \ge 11^{1-\epsilon} k^{2-\epsilon} = k (11 k)^{1-\epsilon}$, which implies $h > k (11 h k)^{1-\epsilon} \ge k n^{1-\epsilon}$.

By moving all the pebbles on a minimum $s$-$t$-cut of $G$ we can show that the inapproximability result provided above is essentially tight for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$:

${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Max}}}$ is $d$-approximable in polynomial time, where $d < n$ is the diameter of $G$, while ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$ is $(k \cdot d)$-approximable in polynomial time.

The approximation algorithm is as follows: if the initial position of the pebbles already makes $s$ and $t$ disconnected, then we are done. Otherwise, compute (in linear time) a minimum $s$-$t$-cut of $G$, say $C$. If $|C| > k$ this implies that both problems have no solution, otherwise move the pebbles on the vertices of $C$. The optimal measure must be at least $1$, while each of the $k$ pebbles travels a distance of at most $d$.

We close this section proving a theorem which is useful in linking the approximability of ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Num}}}$ to that of ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$:

If there exists a $\rho$-approximation algorithm for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Num}}}$ then there exists a $(\rho\cdot d)$-approximation algorithm for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$, where $d < n$ is the diameter of $G$.

Consider an instance of ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$ an let $c^*$ be the measure of an optimal solution. If $c^\prime$ is the measure of the optimal solution on ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Num}}}$, then $c^* \ge c^\prime$. If $c^\prime = 0$ the claim is trivial, therefore we consider $c^\prime > 0$. Then, a $\rho$-approximate solution for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Num}}}$ is a $\rho \cdot d$-approximate solution for ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Sum}}}$, as each pebble travels a distance of at most $d$, and $\frac{\rho\cdot d \cdot c^\prime}{c^*} \le \frac{\rho\cdot d \cdot c^\prime}{c^\prime} = \rho \cdot d$.

Conclusions {#sec:concl}
===========

In this paper we have been concerned with the emerging field of (centralized) pebble motion problems. In particular, we have provided approximability and inapproximability results –most of which were tight– for several relevant variants studied in the literature. Among the issues we left open, the most prominent are those of establishing whether ${\ensuremath{\textsc{Ind}}}$-${\ensuremath{\textsc{Max}}}$ on trees can be solved in polynomial time, and of settling the computational complexity of ${\ensuremath{s\mbox{-}t\mbox{-}\textsc{Cut}}}$-${\ensuremath{\textsc{Num}}}$.

Motion planning of devices in a constrained environment deserves a further deep investigation in several respects. Here we have limited our attention to vertex-to-vertex motion on unweighted, undirected graphs, and with the objective of achieving very basic configurations, but it is easy to imagine more challenging scenarios. For instance, pebbles could be deployed on a 2-dimensional environment, or even on a terrain. In this case, the planning task could become substantially more difficult, because of the setting in the continuum. On the other hand, a simplifying yet very interesting scenario is that in which the given graph is a 2-dimensional grid. At an intermediate stage, an intriguing variant is that in which the underlying graph is weighted. We also plan to look at other goal configurations, e.g., reaching a set of vertices inducing a 2-edge-connected subgraph, or connected subgraph with a bounded diameter, just to mention few.

Acknowledgements {#acknowledgements .unnumbered}
================

We would like to thank Feliciano Colella and Simone Galanti for insightful discussions on computational tractability of some of the problems studied in this paper.

[99]{}

Ahmadian, S., Friggstad, Z., Swamy, C.: Local-search based approximation algorithms for mobile facility location problems. *Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’13)*, SIAM, 1607–1621, 2013.

Bilò, D., Disser, Y., Gualà, L., Mihal’ak, M., Proietti, G., Widmayer, P.: Polygon-constrained motion planning problems. *Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS’13)*, LNCS 8243, Springer, 67–82, 2013.

Berman, P., Demaine, E.D., Zadimoghaddam, M.: $O(1)$-approximations for maximum movement problems. *Proocedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and of the the 15th International Workshop on Randomization and Computation (APPROX-RANDOM’11)*, LNCS 6845, Springer, 62–74, 2011.

Bollob[á]{}s, B.: *Modern Graph Theory 184*, Springer, 1998.

Bomze, I.M., Budinich, M., Pelillo, M., Rossi, C.: Annealed replication: a new heuristic for the maximum clique problem. *Discrete Applied Mathematics* 121(1-3):27–49, 2002.

Demaine, E.D., Hajiaghayi, M.T., Mahini, H., Sayedi-Roshkhar, A.S., Gharan, S.O., Zadimoghaddam, M.: Minimizing movement. *ACM Transactions on Algorithms* 5(3), article 30, 2009.

Demaine, E.D., Hajiaghayi, M., Marx, D.: Minimizing movement: fixed-parameter tractability. *Proceedings of the 17th Annual European Symposium on Algorithms (ESA’09)*, LNCS 5757, Springer, 718–729, 2009.

Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. *Annals of Mathematics*, 439–485, 2005.

Friggstad, Z., Salavatipour, M.R.: Minimizing movement in mobile facility location problems. *ACM Transactions on Algorithms* 7(3), article 28, 2011.

Hall, P.: On representatives of subsets. *Journal of the London Mathematical Society* 10(1):26–30, 1935.

Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: *Domination in graphs: advanced topics 40*, Marcel Dekker, New York, 1998.

Khot, S.: On the power of unique 2-prover 1-round games. *Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC’02)*, ACM, 767–775, 2002.

Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. *Journal of Computer and System Sciences* 74(3):335–349, 2008.

Prencipe, G., Santoro, N.: Distributed algorithms for autonomous mobile robots. *Proceedings of the 4th International Conference on Theoretical Computer Science (IFIP-TCS’06)*, IFIP 209, Springer, 47–62, 2006.

[^1]: Research partially supported by the Research Grant PRIN 2010 “ARS TechnoMedia” funded by the Italian Ministry of University and Research.

[^2]: A preliminary version of this work appeared in the *Proceedings of the 20th Colloquium on Structural Information and Communication Complexity (SIROCCO’13)*, LNCS 8179, Springer, 322–333, 2013. DOI: http://dx.doi.org/10.1007/978-3-319-03578-9\_27

[^3]: A centroid of a tree is a vertex whose removal minimizes the maximum number of nodes over all the trees of the resulting forest. Notice that each tree of the forest has at most half of the vertices of the original tree, and that a centroid can be easily found in linear time.

[^4]: This is not true if $G$ is a tree: take the tree $T$ with vertex set $\{1, 2, \dots, 11\}$ and edge set $\{ (i,i+1) : 1 \le i \le 4 \} \cup \{ (2,6), (2,7), (3,8),(3,9), (4,10), (4,11) \}$, place $2$ pebbles on vertex $1$ and one pebble on each vertex in $\{6, 7, 8, 9, 10, 11\}$. It is easy to see that any optimal solution has cost $3$ and that at least one edge must be traversed in opposite directions.

[^5]: The case $\mu(p_i) = \mu(p_{i+1})$ is clearly impossible.

[^6]: Notice that the additional vertex $u$ is only instrumental to guarantee that $G$ is connected.

[^7]: W.l.o.g. we assume that $Q$ contains no vertices of weight $0$.
