# Monotone circuit representations of paths in a graph?

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?