<p>In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide
whether there is a path between <b>all</b> $n^2$ pairs $(s,t)$ of vertices.
In its special case, STCONN, the task is only for <b>one</b> 
fixed pair $(s,t)$ of vertices. I am  interested in 
the size of <b>monotone</b> circuits with 
fanin-2 AND and OR gates solving STCONN. </p>

<blockquote>
<b>QUESTION:</b> Does STCONN require monotone boolean circuits of size $\Omega(n^3)$?  
</blockquote>

<p>What I know is:</p>

<ul>
<li> STCONN, and even CONN, can be solved by monotone circuits of size $O(n^3)$: use
well known dynamic programming algorithms of Bellman-Ford for STCONN,
and by Floyd-Warshall for CONN.
<li> Every monotone circuit for STCONN has <b>depth</b> $\Omega(\log^2 n)$:
Karchmer-Wigderson (1990), Grigni-Sipser (1995). By binary search, this depth
is also enough. 
<li> Every monotone circuit for CONN has <b>size</b> $\Omega(n^3)$:
CONN has almost the same monotone complexity as boolean multiplication 
of two boolean matrices, and this latter problem is shown, 
by Paterson (1975) and by Mehlhorn-Galil (1976), to require $\Omega(n^3)$ gates.
</ul>

<p>But what about the <b>size</b> of monotone circuits for <b>STCONN</b>? 
Is this still an open problem? I guess - it is, but would be happy to hear the opposite.</p>

<p><p>
<b>ADDED</b> (on 9.10.2012) My question is related to the question about the status of <b>tropical circuit</b> complexity of "weighted" STCONN 
(the shortest $s$-$t$ path problem); see my <a href="https://cstheory.stackexchange.com/questions/8918/monotone-arithmetic-circuits?rq=1">answer</a>;
a <i>tropical circuit</i> is a circuit with fanin-2 Min and Plus gates.
 Suppose we have a 0/1 optimization problem
$f(x)=\min_{S\in{\cal F}}\sum_{i\in S}x_i$, where ${\cal F}$ is a family of
feasible solutions, and $x_i$'s are real numbers. A "boolean version" of
this problem is a monotone boolean function 
$f_B(x)=\bigvee_{S\in{\cal F}}\bigwedge_{i\in S}x_i$. 
In the case of the shortest $s$-$t$ path problem, $f_B$ is STCONN. 
<p>
If the domain of $f(x)$
contains $0$ and $\infty$, then the minimum size of a tropical circuit
for $f(x)$ is at least the minimum size of a monotone boolean circuit
for $f_B(x)$. This holds because the mapping $h:\{0,\infty\}\to\{0,1\}$ given by $h(0):=1$ and $h(\infty):=0$ is a homomorphish from the semiring $(\{o,\infty\},\min,+)$ to the boolean semiring. But lower bounds for tropical circuits could come easier than for 
monotone boolean circuits: the domain now is huge (real numbers), and 
Min does not distribute over Plus. Hence, an ``easier'' question:  </p>

<blockquote>
Does the shortest $s$-$t$ paths problem requires 
tropical circuits of size $\Omega(n^3)$?  
</blockquote> 

<p>Another model weaker than monotone boolean circuits and tropical circuits is that of
<a href="https://cstheory.stackexchange.com/questions/8918/monotone-arithmetic-circuits?rq=1"><b>monotone arithmetic circuits</b></a>: here no produced monomials can be
cancelled later. We can associate with the weighted STCONN 
a multilinear polynomial $P(x)$ by taking one monomial 
for each simple $s$-$t$ path. Hence, yet ``simpler'' question:</p>

<blockquote>
Does $P(x)$ require monotone arithmetic circuits of size $\Omega(n^3)$?  
</blockquote> 

<p><hr>
<b>ADDED</b> (23.01.2013): The list of known results above is not complete: 
Aaron Potechin has also <a href="http://eccc.hpi-web.de/report/2009/142/" rel="noreferrer">shown</a> that <i>directed</i> STCONN
requires monotone <i>switching networks</i> of size $n^{\Omega(\log n)}$.
Each such network is an <i>undirected</i> graphs with two
distinguished source and target nodes, an with edges labeled by variables. 
When input vector arrives, all edges evaluated to $0$ are removed,
and the vector is accepted iff there is a source-target path in the remaining
subgraph. In contrast, is we would allow a network be <i>directed</i> then
even directed STCONN can be solved (using similar construction as 
<a href="https://cstheory.stackexchange.com/questions/14591/combinatorics-of-bellman-ford-or-how-to-make-cyclic-graphs-acyclic">here</a>)
by a monotone network of size $O(n^4)$, even by an
acyclic network. This is the largest known gap between monotone directed 
and undirected networks!</p>

<p><hr>
<b>CORRECTION</b> (on 21.05.2014): I was wrong with item 3 above: the lower bound $\Omega(n^3)$ for CONN is also not known! The bound on matrix product only gives such a lower bound for APCONN (all-pairs connectivity): this is a <em>set</em> of $n^2$ boolean functions $f_{ij}$ outputing $1$ iff there is a path between nodes $i$ and $j$. The (single-output) function CONN is the AND of all $f_{ij}$. Note that circuits computing CONN need not to compute APCONN: the circuit for CONNN needs not to compute the functions $f_{ij}$ on <em>separate</em> output gates.  </p>

<p><p> 
<b>ADDON</b> (on 21.05.2014): Lower bounds on the monotone <em>depth</em> of CONN are also known: by improving an earlier bound $\Omega(n^{3/2}n/\ln\ln n)$ of Yao (1994), Goldman and Hastad (1998) proved an almost optimal bound of $\Omega(\ln^2/\ln\ln n)$. Interestingly, these bounds were proved not by using the Karchmer-Wigderson games (as it was for STCONN) but rather a form of Razboro's approximation method. 
<p>
<b>ANSWER</b> (on 21.05.2014): My 3-rd (yet ``simpler'') question indeed has a simple answer: monotone arithmetic circuits for the STCONN polynomial $P(x)$ require even <em>exponential</em> size. This holds because: (1) every such circuit must also compute the Hamilton s-t path polynomial HP (monomials are s-t path containing all nodes), and (2) HP requires monotone arithmetic circuits of exponential size (a simple covering-by-rectangles argument since nothing can be cancelled in such circuits).  </p>

CC BY-SA 3.0
2012-10-08T18:54:13.037Z
maybe this is obvious to those working in this area but deserves mention.. the problem would seem to have close connections to [$L$](http://en.wikipedia.org/wiki/L_%28complexity%29), for the undirected case which is called USTCONN and recently shown to be in $L$ in 2004 by Reingold....& from memory there is a close $L$-complete problem (is it USTCONN?)
vzn
CC BY-SA 3.0
2012-10-08T19:26:09.217Z
@vzn: good point! I've should had have mentioned this nice result. But it doesn't help us further. We seek for  **lower** bounds. In a weaker (apparently) model than $L$. Directed or not -- this doesn't matter (as much). Is it easier to have an answer for **one** pair of vertices  as for all $n^2$ vertices -- this is the question.
Stasys
CC BY-SA 3.0
2014-02-19T03:39:27.843Z
hi SJ recently ran across this new ref that seems related, what do you think? [Computing All-Pairs Shortest Paths by Leveraging Low Treewidth](http://arxiv.org/abs/1401.4609) Planken et al.. does it suggest maybe that the worst case graphs have high treewidth?
vzn
<cc.complexity-theory><circuit-complexity><lower-bounds><dynamic-programming><monotone>
Monotone complexity of s-t connectivity
Stasys
# Monotone complexity of s-t connectivity

(Asked by: username_0 on 2012-10-06)

In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide
whether there is a path between **all** $n^2$ pairs $(s,t)$ of vertices.
In its special case, STCONN, the task is only for **one**
fixed pair $(s,t)$ of vertices. I am interested in
the size of **monotone** circuits with
fanin-2 AND and OR gates solving STCONN.

> **QUESTION:** Does STCONN require monotone boolean circuits of size $\Omega(n^3)$?

What I know is:

* STCONN, and even CONN, can be solved by monotone circuits of size $O(n^3)$: use
  well known dynamic programming algorithms of Bellman-Ford for STCONN,
  and by Floyd-Warshall for CONN.* Every monotone circuit for STCONN has **depth** $\Omega(\log^2 n)$:
    Karchmer-Wigderson (1990), Grigni-Sipser (1995). By binary search, this depth
    is also enough.* Every monotone circuit for CONN has **size** $\Omega(n^3)$:
      CONN has almost the same monotone complexity as boolean multiplication
      of two boolean matrices, and this latter problem is shown,
      by Paterson (1975) and by Mehlhorn-Galil (1976), to require $\Omega(n^3)$ gates.

But what about the **size** of monotone circuits for **STCONN**?
Is this still an open problem? I guess - it is, but would be happy to hear the opposite.

**ADDED** (on 9.10.2012) My question is related to the question about the status of **tropical circuit** complexity of "weighted" STCONN
(the shortest $s$-$t$ path problem); see my [answer](https://cstheory.stackexchange.com/questions/8918/monotone-arithmetic-circuits?rq=1);
a *tropical circuit* is a circuit with fanin-2 Min and Plus gates.
Suppose we have a 0/1 optimization problem
$f(x)=\min\_{S\in{\cal F}}\sum\_{i\in S}x\_i$, where ${\cal F}$ is a family of
feasible solutions, and $x\_i$'s are real numbers. A "boolean version" of
this problem is a monotone boolean function
$f\_B(x)=\bigvee\_{S\in{\cal F}}\bigwedge\_{i\in S}x\_i$.
In the case of the shortest $s$-$t$ path problem, $f\_B$ is STCONN.

If the domain of $f(x)$
contains $0$ and $\infty$, then the minimum size of a tropical circuit
for $f(x)$ is at least the minimum size of a monotone boolean circuit
for $f\_B(x)$. This holds because the mapping $h:\{0,\infty\}\to\{0,1\}$ given by $h(0):=1$ and $h(\infty):=0$ is a homomorphish from the semiring $(\{o,\infty\},\min,+)$ to the boolean semiring. But lower bounds for tropical circuits could come easier than for
monotone boolean circuits: the domain now is huge (real numbers), and
Min does not distribute over Plus. Hence, an ``easier'' question:

> Does the shortest $s$-$t$ paths problem requires
> tropical circuits of size $\Omega(n^3)$?

Another model weaker than monotone boolean circuits and tropical circuits is that of
[**monotone arithmetic circuits**](https://cstheory.stackexchange.com/questions/8918/monotone-arithmetic-circuits?rq=1): here no produced monomials can be
cancelled later. We can associate with the weighted STCONN
a multilinear polynomial $P(x)$ by taking one monomial
for each simple $s$-$t$ path. Hence, yet ``simpler'' question:

> Does $P(x)$ require monotone arithmetic circuits of size $\Omega(n^3)$?

---

**ADDED** (23.01.2013): The list of known results above is not complete:
Aaron Potechin has also [shown](http://eccc.hpi-web.de/report/2009/142/) that *directed* STCONN
requires monotone *switching networks* of size $n^{\Omega(\log n)}$.
Each such network is an *undirected* graphs with two
distinguished source and target nodes, an with edges labeled by variables.
When input vector arrives, all edges evaluated to $0$ are removed,
and the vector is accepted iff there is a source-target path in the remaining
subgraph. In contrast, is we would allow a network be *directed* then
even directed STCONN can be solved (using similar construction as
[here](https://cstheory.stackexchange.com/questions/14591/combinatorics-of-bellman-ford-or-how-to-make-cyclic-graphs-acyclic))
by a monotone network of size $O(n^4)$, even by an
acyclic network. This is the largest known gap between monotone directed
and undirected networks!

---

**CORRECTION** (on 21.05.2014): I was wrong with item 3 above: the lower bound $\Omega(n^3)$ for CONN is also not known! The bound on matrix product only gives such a lower bound for APCONN (all-pairs connectivity): this is a *set* of $n^2$ boolean functions $f\_{ij}$ outputing $1$ iff there is a path between nodes $i$ and $j$. The (single-output) function CONN is the AND of all $f\_{ij}$. Note that circuits computing CONN need not to compute APCONN: the circuit for CONNN needs not to compute the functions $f\_{ij}$ on *separate* output gates.

**ADDON** (on 21.05.2014): Lower bounds on the monotone *depth* of CONN are also known: by improving an earlier bound $\Omega(n^{3/2}n/\ln\ln n)$ of Yao (1994), Goldman and Hastad (1998) proved an almost optimal bound of $\Omega(\ln^2/\ln\ln n)$. Interestingly, these bounds were proved not by using the Karchmer-Wigderson games (as it was for STCONN) but rather a form of Razboro's approximation method.

**ANSWER** (on 21.05.2014): My 3-rd (yet ``simpler'') question indeed has a simple answer: monotone arithmetic circuits for the STCONN polynomial $P(x)$ require even *exponential* size. This holds because: (1) every such circuit must also compute the Hamilton s-t path polynomial HP (monomials are s-t path containing all nodes), and (2) HP requires monotone arithmetic circuits of exponential size (a simple covering-by-rectangles argument since nothing can be cancelled in such circuits).

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, dynamic-programming, monotone
> **Comments:**
> **username_1**: maybe this is obvious to those working in this area but deserves mention.. the problem would seem to have close connections to [$L$](http://en.wikipedia.org/wiki/L_%28complexity%29), for the undirected case which is called USTCONN and recently shown to be in $L$ in 2004 by Reingold....& from memory there is a close $L$-complete problem (is it USTCONN?)  
> **username_0**: @vzn: good point! I've should had have mentioned this nice result. But it doesn't help us further. We seek for  **lower** bounds. In a weaker (apparently) model than $L$. Directed or not -- this doesn't matter (as much). Is it easier to have an answer for **one** pair of vertices  as for all $n^2$ vertices -- this is the question.  
> **username_1**: hi SJ recently ran across this new ref that seems related, what do you think? [Computing All-Pairs Shortest Paths by Leveraging Low Treewidth](http://arxiv.org/abs/1401.4609) Planken et al.. does it suggest maybe that the worst case graphs have high treewidth?  

---

## 0 answers

