I'm looking at this algorithm, and I want to get something similar that leaves me with a "long directed path", and two weakly disconnected components (meaning there are no edges from one side to the other).
The algorithm is taken from a paper by Shoham Letzter, available here.
My Attempt:
A naive approach would be to ask each of this $v\in P$ wether they have out neighbours $u\in U$, and then take one of those and move it to $P$, if none exist, we move $v$ to $W$. The main issue I have with this "fix", is that I would end with $P$ a "long" path, and two sets of equal size, $U,W$, but now they're a directed pair instead of being disconnected.
My guess is that I should instead "ask" each vertex $v\in P$ whether it has any out-neighbour in $U$ as before, if not, check if it has any in-neighbours in $U$, if it doesn't have any, we move it to $W$, if it has one, then we treat it as a failed vertex, remove it from $P$, and add it to a failed vertex set $F$.
I don't mind loosing those failed vertices, but I don't have an idea on how to bound the final size of $F$, or if there's a more clever algorithm that would finish with disconnected sets $U,W$ from the get-go.
Any help or reference is greatly appreciated!.