45
$\begingroup$

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; 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: 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 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) 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).

$\endgroup$
  • 4
    $\begingroup$ maybe this is obvious to those working in this area but deserves mention.. the problem would seem to have close connections to $L$, 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?) $\endgroup$ – vzn Oct 8 '12 at 18:54
  • 4
    $\begingroup$ @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. $\endgroup$ – Stasys Oct 8 '12 at 19:26
  • $\begingroup$ hi SJ recently ran across this new ref that seems related, what do you think? Computing All-Pairs Shortest Paths by Leveraging Low Treewidth Planken et al.. does it suggest maybe that the worst case graphs have high treewidth? $\endgroup$ – vzn Feb 19 '14 at 3:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.