Restricting a relation to an injective function

Question

Given a relation between two finite sets, how can I determine whether it restricts to an injective function? The criterion or algorithm doesn't need to be constructive: It is enough to know that such a function exists.

This is not homework; I've racked my memory for mathematical or algorithmic methods, I've considered various ways of projecting from the sets of pairs constituting the relation, but I'm coming up short. Google is only fetching minimum-cost optimizations (e.g., the Munkres assignment algorithm).

There's an obvious graph formulation of this problem (in terms of bipartite graphs), so I'm tagging it graph-theory as well.

Edit: The problem is not as trivial as it may seem. For example, the relation $\{(a,1),(a,2),(a,3),(b,3),(c,3)\}$ does not restrict to an injection, but this fact cannot be demonstrated by examining its domain and image (which are equal in size).

Answer 1

There was just a question on Hall's theorem. Hall's theorem gives a necessary and sufficient condition for a relation from $A$ to $B$ to restrict to an injective function from $A$ to $B$.

The condition is that for all $A' \subset A$, $|n(A')| \geq |A'|$ where $n(A')$ is the set of neighbours of $A'$ in $B$. Naively this would take $2^n$ time to check.

This is also a special case of a maximal matching problem for bipartite graphs. It can be expressed as a maximum-flow problem, and solved in polynomial time using the Ford-Fulkerson algorithm. This algorithm finds a matching.

Answer 2

Let $R \subset A \times B$ be our relation. Compute the two cardinalities $$n=\{ a \in A : \exists b \in B : a R b\}$$ $$m=\{ b \in B : \exists a \in A : a R b\}$$

If these two cardinalities are equal to the cardinality of $A$, then $R$ can be restricted to an injective function, otherwise no.

EDIT: This is only a necessary condition. See comments below for clarifications.