**OP’s condition “$\newcommand{\P}{\mathcal{P}}A \to \P B$ is surjective on singletons” is indeed necessary and sufficient.**

For this, I’ll first give a characterisation that holds just by abstract nonsense: **$R \subseteq A \times B \newcommand{\Rel}{\mathrm{Rel}}$ is epi in $\Rel$ if and only if the associated map $\check{R} : \P B \to \P A$ is injective.** To see this, note by duality it’s equivalent to show that such $R$ is mono precisely if $\hat{R} : \P A \to \P B$ is injective. For this, note that $\hat{R}$ is the image of $R$ under the “forgetful” functor $\Rel \to \newcommand{\Set}{\mathrm{Set}}\Set$ (seeing $\Rel$ as the Kleisli category of the covariant powerset monad). This functor is faithful, so it reflects monos, and it’s representable as $\Rel(1,-)$, so it preserves them.

So $R \subseteq A \times B$ is mono just if $\hat{R} : \P A \to \P B$ is injective, and dually, is epi just if $\check{R} : \P B \to \P A$ is injective. Now I claim **injectivity of $\check{R}$ is equivalent to $\bar{R} : A \to \P B$ being surjective on singletons**, or in other words, that for each $b \in B$, there’s some $a \in A$ that is related just to $b$ under $R$. Assuming $\check{R}$ is injective, we know that $\check{R}(B \setminus \{b\}) \subsetneq \check{R}(B)$, so taking some element of their difference, we get an element of $A$ related just to $b$. Conversely, assuming $\bar{R} : A \to \P B$ is surjective on singletons, then for any $s,t \subseteq B$, take some $b$ in their difference, and some $a$ related just to $b$; then $\check{R}(s)$ and $\check{R}(t)$ are distinguished by $a$.

and surjective, in order to use the fact that the function-to-graph construction preserves epis? Which reduces your second condition to a special case of your first, I think. $\endgroup$