Activating "AND" Nodes and "OR" nodes

Question

Consider a directed graph with AND nodes and OR nodes. The AND nodes are activated only when all the in edges into it are activated. The OR nodes are activated if at least one of the in edges into it is activated. Assuming that vertices with no in edges into them are activated initially, how to design an efficient algorithm to decide if all nodes can be activated? I have thought of some naive algorithm but it takes $O(n^{3})$ time. I believe $n^{3}$ cannot be an efficient algorithm and there's some method that I am missing. Tagging domains where the problem might have a solution.

Answer 1

A little modification to a dfs will work in time $\mathcal O(n^3)$. This dfs wil pass through each vertex at most $n$ times, so at most $n^2$ call to the function dfs are made, and each one takes at most $n$ iterations.

Here is the c++11 code:

#include <bits/stdc++.h>
using namespace std;

const int MAX=1010;
int Ae[MAX]; // stores the number of activated edges going into a vertex
int A[MAX]; // stores if a node is activated
int In[MAX];// stores the number of edges going in
vector <int> Out[MAX];
int Ty[MAX]; // stores the type of node

void dfs(int x){
    if(Ty[x]==0) A[x]=1;// we check if the node should be activated
    if(Ty[x]==1 && Ae[x]== In[x]) A[x]=1;
    if(A[x]==0) return;// if not then we dont go into its neighbours
    for(int y: Out[x]){// otherwise we explore its neighbours
        if(Ae[y] < In[y]){
            Ae[y]++;
            if(A[y]==0) dfs(y);
        }
    }
}

int main(){
    int n,m; 
    scanf("%d %d",&n,&m);// read number of vertices and edges
    for(int i=0;i<n;i++){
        scanf("%d",&Ty[i]); // 1 if the node is AND and 0 if it is OR
    }
    while(m--){// read edges
        int a,b;
        scanf("%d %d",&a,&b);
        Out[a].push_back(b);
        In[b]++;
    }
    for(int i=0;i<n;i++){// we activate the vertices with in degree 0
        if(In[i] == 0 ){
            dfs(i);
        }
    }
    // at the end we can check if vertex i is activated using A[i]
    for(int i=0;i<n;i++){
        printf("%d: %d\n",i,A[i]);
    }
}

Answer 2

A idea would be to iterate over all edges, and from each edge see if a connected node is a AND or a OR node. Put at begin every node to true (activated) . If this node is a OR node, dont do nothing. If a edge is a activated node, we no need to do anything. If our edge is a not activated node, see if each of 2 nodes are OR nodes. If one of them is a AND node, and considering we have a not activated edge, we can assign this node to false (not activated) and exit inmediately, because we can return a value indicating that not all nodes are activated. Time of this algorythm is O(E). Daniel