1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ It may be useful to note that the graph consists of disjoint lassos. Indeed, a strongly connected component in such graph is either: 1) a single vertex v, and the outgoing edge from v leads to another component, or 2) a simple cycle. $\endgroup$ Dec 28 '20 at 11:35
  • $\begingroup$ I note now after seeing Yuval's answer that we actually get (by the above observation) more than disjoint lassos. For example, you can have two vertices $u$ and $v$ in different components, and each of $u$ and $v$ have an outgoing edge that leads to the same cycle in a third component. $\endgroup$ Dec 28 '20 at 19:24
  • $\begingroup$ Is there a special name for these kind of graphs besides "lassos" or something similar? Googling "lassos graphs" didn't help and I want to learn more about them $\endgroup$ Dec 28 '20 at 19:32
  • $\begingroup$ Not that i'm familiar with. But the structure is simple: every maximal strongly connected component (MSCC, for short) is either trivial (one vertex) or is a simple cycle. Also, as the each vertex has outdegree 1, the cycle MSCCs are ergodic (they have no outgoing edges that lead to a different MSCC), and trivial MSCCs have one successor (lead to one MSCC). So, you have a forest of MSCCs which is a collection of trees where the root nodes are cycles. So the directed paths ending with cycles (known as lassos) can meet before the ending cycle, or lead to the same cycle. $\endgroup$ Dec 28 '20 at 20:10
3
$\begingroup$

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})$.

$\endgroup$
11
  • $\begingroup$ So from what I understand in the graph there will be directed cycles, directed paths that end up pointing to a component of the cycle and directed paths that end up pointing to a component of another directed path. Will post in comments 2 examples too see if I get this right. $\endgroup$ Dec 28 '20 at 18:13
  • $\begingroup$ imgur.com/a/yOppKZV . The length of the cycle $ 3 \rightarrow 4 \rightarrow 5 \rightarrow 3 $ is 3 so $ l = 1$ and for : $ 1 \rightarrow 2 \rightarrow 3$ $ r_1 = 1 $ , $ 8 \rightarrow 3 $ $ r_2 = 1 $ , $ 6 \rightarrow 3 $ $ r_3 = 1 $ , $ 7 \rightarrow 5 $ $ r_4 = 1 $ and so the size of the independent set is $l + r_1 + r_2 + r_3 + r_4 = 5 $ $\endgroup$ Dec 28 '20 at 18:25
  • $\begingroup$ imgur.com/a/AIHHJFN .Once again the length of the cycle $ 3 \rightarrow 4 \rightarrow 5 \rightarrow 3 $ is 3 so $ l = 1$ and for : $ 1 \rightarrow 2 \rightarrow 3$ - $ r_1 = 1 $ , $ 8 \rightarrow 2 $ - $ r_2 = 1 $ , $ 6 \rightarrow 3 $ - $ r_3 = 1 $ , $ 7 \rightarrow 5 $ - $ r_4 = 1 $ and so the size of the independent set is$l + r_1 + r_2 + r_3 + r_4 = 5 $ once again . From what I understand if a directed path points to a component of another directed path this does not change the MIS size . $\endgroup$ Dec 28 '20 at 18:37
  • $\begingroup$ Right, actually you get more than "lassos". This does change the size of the MIS. For example, consider a $2$-cycle with $m$ vertices pointing at one of the vertices. The MIS is $m+1$. In contrast, if the $m$ vertices were arranged in a cycle, the answer would be $\lceil m/2 \rceil + 1$. $\endgroup$ Dec 28 '20 at 19:08
  • 1
    $\begingroup$ Here you get the MIS itself for free. $\endgroup$ Dec 28 '20 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.