I was given this special type of Directed Graph and was asked to find it's Maximum Independent Set.
Graph Properties :
- Graph has $N$ vertices and $N$ edges
- There can be no edge from a vertex $v$ to itself
- Each vertex $v$ has only 1 outgoing edge and 0 or more incoming edges
I framed this problem as a linked list with potentially some cycles. So far I've tried a DFS approach, two Greedy ones and right now I am thinking of a DP one trying to convert the linked list to a Binary Tree by removing the cycles somehow.
All of the approaches below respect the fact that there can be no edges between vertices of the under construction independent set.So when a vertex is under consideration to be a member of it I check if it points to a vertex of the under construction independent set.
First Greedy approach :
Sort the vertices based on the number of incoming edges and keep taking the ones with the least incoming edges let's call them $v_1,v_2...$ as well as the ones who point where $v_1,v_2...$ do as they are basically free and so on.
Second Greedy approach :
Take the ones with no incoming edges let's call them $z_1,z_2...$ as well as the ones who point where $z_1,z_2...$ do as they are basically free as well and from there see which vertices have the most incoming edges and take the ones who point at them.
Both approaches seem to fail by 1 in some test cases.
As for the DFS one it was something like take 2 a time where in $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_5$ I would take $v_1,v_3,v_5..$ and so on.
I also tried prioritizing the ones with 0 incoming edges in the DFS approach but no luck and I think I am in the right direction but I am missing a small detail.
Any thoughts or insight would be really helpful.