Maximum Independent Set of special Directed Graph

Question

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.

Answer 1

The type of graph you are describing is identical to the one encountered in Pollard's rho algorithm. Connected components of your graph are cycles with directed trees feeding into them (possibly none). It follows that it suffices to solve your problem for such graphs.

The first step is to compute, for each directed tree, the maximum size of an independent set, depending on whether the root is included or not. Denote the maximum size of an independent set in the first case by $\alpha_+(T)$, and in the second case by $\alpha_-(T)$, and let $\alpha(T) = \max(\alpha_+(T),\alpha_-(T))$. If $T$ is a single vertex then $\alpha_+(T) = 1$ and $\alpha_-(T) = 0$. If $T$ is composed of a root and subtrees $T_1,\ldots,T_d$, then $\alpha_+(T) = \alpha_-(T_1) + \cdots + \alpha_-(T_d) + 1$, and $\alpha_-(T) = \alpha(T_1) + \cdots + \alpha(T_d)$.

Now suppose that we have a cycle of length $\ell$, and let $T_1,\ldots,T_\ell$ be the directed trees whose roots are the vertices of the cycle (the trees could be single vertices). Let $\alpha_{\pm_1,\pm_2,i}$ be the maximum size of an independent set in $T_1,\ldots,T_i$ which contains the root of $T_1$ according to the first $\pm$, the root of $T_i$ according to the second $\pm$, and which doesn't contain two adjacent roots. First, $\alpha_{\pm,\pm,1} = \alpha_\pm(T_1)$, and $\alpha_{\pm,\mp,1} = 0$. Second, $\alpha_{\pm,+,i+1} = \alpha_{\pm,-,i} + \alpha_+(T_{i+1})$ and $\alpha_{\pm,-,i+1} = \max(\alpha_{\pm,+,i},\alpha_{\pm,-,i}) + \alpha_-(T_{i+1})$. Finally, the maximum size of an independent set of the entire component is $\max(\alpha_{+,-,\ell},\alpha_{-,+,\ell},\alpha_{-,-,\ell})$.