Partitioning vertices in a bipartite graph according to minimum vertex covers
The following idea comes from a Chinese blog.

Find a maximum matching $M$ ($2m$ vertices and $m$ edges) firstly. For convenience, for a vertex $v$, we denote by $M(v)$ the vertex that is matched with $v$ in $M$, and denote by $N(v)$ the set of neighbors of $v$.

We have the following observations:


All vertices not in $M$ must belong to $\mathrm{Never}$.

Proof. Suppose a minimum vertex cover contains a vertex $v$ not in $M$, to cover the $m$ edges in $M$, the vertex cover must also contains another $m$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.
If a vertex $v$ in $M$ belongs to $\mathrm{Always}$, then $M(v)$ must belong to $\mathrm{Never}$. 

Proof. Suppose a minimum vertex cover contains both $v$ and $M(v)$, to cover the rest $m-1$ edges in $M$, the vertex cover must also contains another $m-1$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.
If a vertex $v$ belongs to $\mathrm{Never}$, then $N(v)$ must be a subset of $\mathrm{Always}$. 


These observations lead us to the following algorithm:

A = A[0] = empty set
N = N[0] = all the vertices not in M
i = 0
while True:
    i = i + 1
    A[i] = empty set
    for each vertex v in N[i - 1]:
        temp = N(v) \ A
        A[i] = union(A[i], temp)
        A = union(A, temp)

    if A[i] is empty:
        break

    for each vertex v in A[i]:
        add M(v) into N[i]
        add M(v) into N


After the execution of this algorithm, all vertices in A belong to $\mathrm{Always}$ and all vertices in N belong to $\mathrm{Never}$. For those rest vertices, we partition them into two sides by intersecting respectively with $L$ and $R$, where $L$ and $R$ are respectively the two sides of the bipartite graph. We can see either side along with the vertices in A forms a minimum vertex cover, so these vertices belong to $\mathrm{Exist}$.