The Acquaintance Time of a Graph

We define the following parameter of connected graphs.
For a given graph $G = (V,E)$ we place one agent in each vertex $v \in V$.
Every pair of agents sharing a common edge are said to be acquainted.
In each round we choose some matching of $G$ (not necessarily a maximal matching),
and for each edge in the matching the agents on this edge swap places.
After the swap, again, every pair of agents sharing a common edge are acquainted,
and the process continues. We define the \emph{acquaintance time}
of a graph $G$, denoted by $\AC(G)$, to be the minimal number of rounds required
until every two agents are acquainted.

We first study the acquaintance time for some natural families of graphs
including the path, expanders, the binary tree, and the complete bipartite
graph. We also show that for all functions $f : \N \to \N$ satisfying
$1 \leq f(n) \leq n^{1.5}$ there is a family of graphs
$\{G_n = (V_n,E_n)\}_{n \in \N}$ with $|V_n| = n$ such that
$\AC(G_n) = \Theta(f(n))$.
We also prove that for all $n$-vertex graphs $G$ we have
$\AC(G) = O\left(\frac{n^2}{\log(n)/\log\log(n)}\right)$,
thus improving the trivial upper bound of $O(n^2)$
achieved by sequentially letting each agent perform depth-first search
along some spanning tree of $G$.

Studying the computational complexity of this problem, we prove that for any
constant $t \geq 1$ the problem of deciding that a given graph $G$ has
$\AC(G) \leq t$ or $\AC(G) \geq 2t$ is $\NP$-complete. That is, $\AC(G)$ is
$\NP$-hard to approximate within multiplicative factor of 2, as well as within
any additive constant factor.

On the algorithmic side, we give a deterministic polynomial time algorithm
that given an $n$-vertex graph $G$ distinguishes between the cases
$\AC(G)=1$ and $\AC(G) \geq n-O(1)$. We also give a randomized
polynomial time algorithm that distinguishes between the cases
$\AC(G)=1$ and $\AC(G) = \Omega(\log(n))$ with high probability.