  We consider the gathering task by a team of $m$ synchronous mobile robots in
a graph of $n$ nodes. Each robot has an identifier (ID) and runs its own
deterministic algorithm, i.e., there is no centralized coordinator. We consider
a particularly challenging scenario: there are $f$ Byzantine robots in the team
that can behave arbitrarily, and even have the ability to change their IDs to
any value at any time. There is no way to distinguish these robots from
non-faulty robots, other than perhaps observing strange or unexpected
behaviour. The goal of the gathering task is to eventually have all non-faulty
robots located at the same node in the same round. It is known that no
algorithm can solve this task unless there at least $f+1$ non-faulty robots in
the team. In this paper, we design an algorithm that runs in polynomial time
with respect to $n$ and $m$ that matches this bound, i.e., it works in a team
that has exactly $f+1$ non-faulty robots. In our model, we have equipped the
robots with sensors that enable each robot to see the subgraph (including
robots) within some distance $H$ of its current node. We prove that the
gathering task is solvable if this visibility range $H$ is at least the radius
of the graph, and not solvable if $H$ is any fixed constant.
