  Over the years, much research involving mobile computational entities has
been performed. From modeling actual microscopic (and smaller) robots, to
modeling software processes on a network, many important problems have been
studied in this context. Gathering is one such fundamental problem in this
area. The problem of gathering $k$ robots, initially arbitrarily placed on the
nodes of an $n$-node graph, asks that these robots coordinate and communicate
in a local manner, as opposed to global, to move around the graph, find each
other, and settle down on a single node as fast as possible. A more difficult
problem to solve is gathering with detection, where once the robots gather,
they must subsequently realize that gathering has occurred and then terminate.
  In this paper, we propose a deterministic approach to solve gathering with
detection for any arbitrary connected graph that is faster than existing
deterministic solutions for even just gathering (without the requirement of
detection) for arbitrary graphs. In contrast to earlier work on gathering, it
leverages the fact that there are more robots present in the system to achieve
gathering with detection faster than those previous papers that focused on just
gathering. The state of the art solution for deterministic gathering~[Ta-Shma
and Zwick, TALG, 2014] takes $\Tilde{O}$$(n^5 \log \ell)$ rounds, where $\ell$
is the smallest label among robots and $\Tilde{O}$ hides a polylog factor. We
design a deterministic algorithm for gathering with detection with the
following trade-offs depending on how many robots are present: (i) when $k \geq
\lfloor n/2 \rfloor + 1$, the algorithm takes $O(n^3)$ rounds, (ii) when $k
\geq \lfloor n/3 \rfloor + 1$, the algorithm takes $O(n^4 \log n)$ rounds, and
(iii) otherwise, the algorithm takes $\Tilde{O}$$(n^5)$ rounds. The algorithm
is not required to know $k$, but only $n$.
