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
    Please may you describe your O(m^3) algorithm?2011-06-28
  • 0
    @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.2011-06-28
  • 0
    I reformulated this question: now $s_i$ are always non-empty but can go outside $[1,m]$.2011-06-28
  • 0
    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?2011-06-28
  • 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