We investigate the probabilistic communication complexity
(more exactly, the majority communication complexity,)
of the graph accessibility problem GAP and
its counting versions MOD_k-GAP, k > 1.
Due to arguments concerning matrix variation ranks
and certain projection reductions, we prove
that, for any partition of the input variables,
GAP and MOD_k-GAP have majority communication complexity
\Omega(n), where n denotes the number of nodes of the
graphs under consideration.