# 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?

I still do not have any ideas about the general answer to this question, but I think I have an argument against the possibility to construct such a circuit in so-called monotone "decomposable negation normal form" or monotone DNNF. This is a circuit with no negations where, for every AND-gate, the inputs do not "depend" on any common variable, i.e., there is no variable $$x$$ having a path to two different inputs of an AND-gate: see this paper for the formal definition.
A monotone DNNF $$C$$ for $$\phi_G$$ can be used to compute the shortest path from $$s$$ to $$t$$ under any weighting of $$G$$ (with positive or negative weights), if we interpret $$C$$ in the tropical semiring: simply replace every variable by the weight of the corresponding edge, interpret AND-gates as a plus, and interpret OR-gates as a max, then the result is the smallest possible weight of a path. (The fact that the circuit is a DNNF is intuitively used to ensure that we do not add a gate with itself.)
Thus, if we could compute in linear time a monotone DNNF for $$\phi_G$$, then we could compute the shortest path from $$s$$ to $$t$$ in linear time. This would be better than the running time of the Bellman-Ford algorithm. This is suspicious, given that it is known to be optimal when using Min and Sum operations: see this paper.