I am interested in the following. Let the inputs of the circuit correspond to the arcs of a directed graph. The circuit has to output 1 iff there is a directed path from a given node S to a given node T such that all arcs on that path have input value 1.
I can construct Boolean circuits that have size linear in nm where n is the number of vertices in the graph and m is the number of arcs. I would like to know if smaller circuits are possible. Especially, circuits that are linear in n+m.