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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.