Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Please may you describe your O(m^3) algorithm? –  Ben Derrett Jun 28 '11 at 9:37
    
@Ben Derrett: Is it necessary? I need to do some work to make it formal - that's why I am looking for existing solutions of the problem. Moreover it seems to me that $\mathcal O(m^3)$ is too slow. –  Ilya Jun 28 '11 at 9:44
    
I reformulated this question: now $s_i$ are always non-empty but can go outside $[1,m]$. –  Ilya Jun 28 '11 at 9:47
    
The problem still looks trivial. Isn't the largest absorbing set $[1, m]$ unless $\exists i : s_i \not\subset [1,m]$ in which case there is no absorbing set? –  Peter Taylor Jun 28 '11 at 10:46
    
@Peter Taylor: Say, $m=3, n=10$ and $s_1 = \{10\}, s_2 = \{2\},s_3 = \{2,9\}$ then $A=\{2\}$. –  Ilya Jun 28 '11 at 10:59

2 Answers 2

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

share|improve this answer
    
For the first turn you remove all $i$ such that $s_i\setminus A' \neq \emptyset$. This will require $mn$ operations. But then you should remove all $i$ which can reach the complement of the set obtained on the previous turn. Number of turns is bounded by $m$, so the running time is $\mathcal O(m^2n)$ - by the way, I edited my question, I meant $\mathcal O(m^2n)$ for my algorithm. –  Ilya Jun 28 '11 at 11:51
    
@Gortaur, the first paragraph is the intuition. The second paragraph is the algorithm, so that's what you need to look at for running time. –  Peter Taylor Jun 28 '11 at 12:05
    
could you please extend the description of an algorithm? I am not so experience with graph theory. –  Ilya Jun 28 '11 at 12:30

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
share|improve this answer
    
I think your algorithm can be also commented in the same way as an answer by Peter. –  Ilya Jun 28 '11 at 11:55
    
@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. –  Jens Jun 28 '11 at 12:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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