1
$\begingroup$

Consider a $m\times n,m\leq n$ matrix $P = (p_{ij})$ such that $p_{ij}$ is either $0$ or $1$ and for each $i$ there is at least one $j$ such that $p_{ij} =1$. Denote $s_i = \{1\leq j\leq n:p_{ij} = 1\}$ so $s_i$ is always non-empty.

We call a set $A\subseteq [1,m]$ absorbing if for all $i\in A$ holds $s_i\subset A$. If I apply my results directly then I will have an algorithm with a complexity of $\mathcal{O}(m^2n)$ which will find the largest absorbing set.

On the other hand I was not focused on developing this algorithm and hence I wonder if you could advise me some algorithms which are faster?

P.S. please retag if my tags are not relevant.

Edited: I reformulate the question (otherwise it was trivial).

I think this problem can be considered as a searching for the largest loop in the graph(if we connect $i$ and $j$ iff $p_{ij} = 1$).

  • 0
    @Peter Taylor: Say, $m=3, n=10$ and $s_1 = \{10\}, s_2 = \{2\},s_3 = \{2,9\}$ then $A=\{2\}$.2011-06-28

2 Answers 2

1

Since you have to look at every entry at least once to find $A_{\max}$ (the largest absorbing set), the time complexity of any algorith cannot be lower than $\mathcal{O}(n\times m)$. I think the algorithm below achives that.

Let $A_i$ be the smallest absorbing set containing $i$ or empty if $i$ is not part of an absorbing set. To find $A_i$, the algorithm starts with $s_i$ and joins is with every $A_j$ for $j\in s_i$. It uses caching to avoid calculating $A_j$ twice. $A_{\max}$ should be the union of all $A_i$s.

A_max := empty set for i from 1 to m   merge A_max with result from explore(i)  explore(i)     if i  is already explored        return known result     else       for j from m + 1 to n         if p_ij = 1            return empty set        A_i := empty set       for j from 1 to m         if p_ij = 1               add j to A_i           if i not equal to j                  A_j = explore(j)             if A_j is empty then               return empty set             else               merge A_i with A_j        return A_i 
  • 0
    @Gotaur: You mean I got a runtime of $\mathcal O(m^2n)$? I don't think so. As you can see, for every $i,j$ $p_{ij}$ is looked at (the if line) exactly once outside of the set merges. But I am quite sure that those can be done in constant time. The recursion does not add to the runtime, since results are cached.2011-06-28
1

One way to think about this is that the largest candidate absorbing set is $A^\prime = [1, m]$. Then while $A^\prime$ contains an element which doesn't meet the condition, we remove that element. When there's nothing left to remove, we have the largest possible absorbing set.

This can be rephrased by thinking of $A$ as a graph adjacency matrix. Then you want to remove all nodes which are reachable from a node $v \in [m+1, n]$. They are easily identified by depth-first search or breadth-first search. For clarity you might want to insert a pseudonode $n+1$ which has edges to each $v \in [m+1, n]$. The running time is $O(mn)$.

  • 0
    could you please extend the description of an algorithm? I am not so experience with graph theory.2011-06-28