Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every path $\pi$ from $s$ to $t$ gives a clause where we conjoin all edges of $\pi$, and $\phi_G$ is the disjunction of all these clauses. (It is obvious that it suffices to only consider simple paths: any path containing a vertex multiple times must use a set of edges that is not minimal under inclusion, so it defines a clause which is absorbed by another.)
If $G$ is required to be an acyclic graph, then I can easily construct in linear time from $G$ a representation of $\phi_G$ as a monotone Boolean circuit (using operators $\lor$ and $\land$). Specifically, every node of $G$ gives a gate of the circuit, which is the constant-1 gate for $t$, and which is otherwise the disjunction, over all outgoing edges $e$, of the conjunction of the variable corresponding to $e$, and of the gate for the end vertex of $e$. (Incidentally, the functions $\phi_G$ for $G$ an acyclic graph do not seem to achieve all possible monotone Boolean functions, and I don't know what is the precise class of functions that are achieved.)
My question is: for a general (non-acyclic) graph $G$, can I also construct in linear time a representation of $\phi_G$ as a monotone Boolean circuit? (or even as a non-monotone Boolean circuit?) I know it can be done in quadratic time, intuitively by making $G$ acyclic by creating $n$ copies of it. But I don't know how to do it in linear time in this case. I suspect it is impossible (and that it could be shown on specific graph classes, e.g., grid graphs), but I don't know how to show it. Are there any relevant circuit lower bounds that could help here?
