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?


1 Answer 1


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.

I do not know, however, if this argument can extend to a lower bound on arbitrary circuits. It seems intuitively implausible that we can make the circuit smaller by conjoining a variable with itself (i.e., using the fact that "x AND x = x" in the Boolean semiring), but I do not know how to prove it.

Edit: another item of related work: in this paper the Boolean function in question is called the "st-connectivity function" (on multigraphs). They mention a result that the function can be represented by a read-once formula precisely for two-terminal series-parallel graphs, but they don't seem to study size bounds.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.