<p>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 &quot;decomposable negation normal form&quot; or monotone DNNF. This is a circuit with no negations where, for every AND-gate, the inputs do not &quot;depend&quot; on any common variable, i.e., there is no variable <span class="math-container">$x$</span> having a path to two different inputs of an AND-gate: see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.110.8260&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">this paper</a> for the formal definition.</p>
<p>A monotone DNNF <span class="math-container">$C$</span> for <span class="math-container">$\phi_G$</span> can be used to compute the shortest path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> under any weighting of <span class="math-container">$G$</span> (with positive or negative weights), if we interpret <span class="math-container">$C$</span> in the <a href="https://en.wikipedia.org/wiki/Tropical_semiring" rel="nofollow noreferrer">tropical semiring</a>: 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.)</p>
<p>Thus, if we could compute in linear time a monotone DNNF for <span class="math-container">$\phi_G$</span>, then we could compute the shortest path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> in linear time. This would be better than the running time of the <a href="https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm" rel="nofollow noreferrer">Bellman-Ford algorithm</a>. This is suspicious, given that it is known to be optimal when using Min and Sum operations: see <a href="https://www.sciencedirect.com/science/article/pii/S0304397516002073" rel="nofollow noreferrer">this paper</a>.</p>
<p>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 &quot;x AND x = x&quot; in the Boolean semiring), but I do not know how to prove it.</p>
<p><strong>Edit:</strong> another item of related work: in <a href="https://arxiv.org/abs/2208.03810" rel="nofollow noreferrer">this paper</a> the Boolean function in question is called the &quot;st-connectivity function&quot; (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.</p>

CC BY-SA 4.0
2021-12-05T21:14:24.593Z
2022-09-06T14:35:53.730Z
2022-09-06T14:35:53.730Z
Antoine Amarilli 'a3nm'
<p>Consider a directed graph <span class="math-container">$G = (V, E)$</span> with a source <span class="math-container">$s \in V$</span> and sink <span class="math-container">$t \in V$</span>. From <span class="math-container">$G$</span>, I can define a monotone Boolean function <span class="math-container">$\phi_G$</span> on the set of variables <span class="math-container">$E$</span>, in the following way: every path <span class="math-container">$\pi$</span> from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> gives a clause where we conjoin all edges of <span class="math-container">$\pi$</span>, and <span class="math-container">$\phi_G$</span> 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.)</p>
<p>If <span class="math-container">$G$</span> is required to be an <em>acyclic</em> graph, then I can easily construct in linear time from <span class="math-container">$G$</span> a representation of <span class="math-container">$\phi_G$</span> as a monotone Boolean circuit (using operators <span class="math-container">$\lor$</span> and <span class="math-container">$\land$</span>). Specifically, every node of <span class="math-container">$G$</span> gives a gate of the circuit, which is the constant-1 gate for <span class="math-container">$t$</span>, and which is otherwise the disjunction, over all outgoing edges <span class="math-container">$e$</span>, of the conjunction of the variable corresponding to <span class="math-container">$e$</span>, and of the gate for the end vertex of <span class="math-container">$e$</span>. (Incidentally, the functions <span class="math-container">$\phi_G$</span> for <span class="math-container">$G$</span> 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.)</p>
<p>My question is: <strong>for a general (non-acyclic) graph <span class="math-container">$G$</span>, can I also construct in linear time a representation of <span class="math-container">$\phi_G$</span> as a monotone Boolean circuit?</strong> (or even as a non-monotone Boolean circuit?) I know it can be done in quadratic time, intuitively by making <span class="math-container">$G$</span> acyclic by creating <span class="math-container">$n$</span> 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?</p>

<graph-theory><circuit-complexity><boolean-functions><directed-acyclic-graph><circuits>
Monotone circuit representations of paths in a graph?
Antoine Amarilli 'a3nm'
# Monotone circuit representations of paths in a graph?

(Asked by: username_0 on 2021-04-01)

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?

**Tags:** graph-theory, circuit-complexity, boolean-functions, directed-acyclic-graph, circuits


---

## 1 answers

### Answer by username_0 on 2021-12-05. Score: 3

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.110.8260&rep=rep1&type=pdf) 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm). This is suspicious, given that it is known to be optimal when using Min and Sum operations: see [this paper](https://www.sciencedirect.com/science/article/pii/S0304397516002073).

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](https://arxiv.org/abs/2208.03810) 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.


---

