16
$\begingroup$

Has anybody seen the following (or similar) question being considered:

Can it be easier to determine the presence/absence of $s$-$t$ paths than to determine the presence/absence of short $s$-$t$ paths?

A bit more formally, the distance-$k$ connectivity problem STCON(n,k) is, given a subgraph of a complete undirected graph $K_n$ on $[n]=\{1,\ldots,n\}$, to decide whether there is a path from node $s=1$ to node $t=n$ of length $\leq k$. By the length, I mean the number of inner nodes (just for notational convenience). The connectivity problem STCON(n) corresponds to the case when $k=n-2$: is there any $s$-$t$ path at all? These problems are monotone boolean functions of $\binom{n}{2}$ variables $x_{i,j}$ corresponding to the edges of $K_n$.

It is well known, that $O(kn^2)$ fanin-$2$ AND and OR gates are enough to compute STCON(n,k). The desired monotone circuit is given by Bellman-Ford: first compute $F_j^{(0)}=x_{s,j}$ for all nodes $j$, and then use the recursion $F_j^{(l+1)}=\bigvee_{i\in[n]} F_i^{(l)}\land x_{i,j}$. Then $F_j^{(l)}$ accepts a given graph iff it has an $s$-$j$ path of length $\leq l$. Hence, $F_n^{(k)}=$STCON(n,k).

Question 1: Can STCON(n) have more than constant times smaller monotone circuits than STCON(n,k), for some $k\ll n$?

A boolean function $f(x_1,\ldots,x_n)$ is a monotone projection of a boolean function $g(y_1,\ldots,y_m)$, if the function $f$ can be obtained from $g$ by replacing each $y$-variable by $0$ or $1$ or by some $x$-variable. Say, we trivially have that every THRESHOLD(n,k) is a monotone projection of MAJORITY(2n).

By taking $k$ copies of the input graph for STCON(n,k), one can easily show that STCON(n,k) is a monotone projection of STCON(kn). Thus, STCON(kn) cannot have smaller circuits than STCON(n,k). Can the factor "k" here be replaced by some constant?

Question 2: Is STCON(n,k) a monotone projection of STCON(m) for some $m < kn$?

ADDDED (Apr.7 ): Among related results I know are the following:

  1. STCON and monotone NC$^1$: if a boolean function $f$ has a monotone formula of size $s$, then $f$ is a monotone projection of STCON(m) for $m=O(s)$; this is easy: just view formulas as parallel-sequential networks. In particular, this implies that every monotone boolean function of $n$ variables is a monotone projection of STCON(m) for some $m\leq n2^n$ (take a monotone DNF).
  2. STCON itself is not in monotone NC$^1$: every monotone circuit for STCON(n,k) requires depth about $(\log k)(\log n)$ (independent on circuit size!). This was shown by Karchmer and Wigderson. As observed by Grigni and Sipser, this holds even when AND gates are allowed to have unbounded fanin! If, however, OR gates can have large fanin and AND gates have fanin-$2$, then depth $2\log k$ and size $O(n^3\log k)$ is already enough: repeated squaring of the adjacency matrix $\log k$ times.
  3. $s$-$t$ Connectivity vs. Connectivity: If $f=x_1x_2\lor x_3x_4\lor\cdots\lor x_{n-1}x_n$ is a monotone projection of CONN(m), then $m\geq 2^n+1$. This was proved by Skyum and Valiant. Here CONN is a "sibling" of STCON: accepts a graph iff it is connected. Note that this particular function $f$ is a monotone projection of STCON(m) even for $m=n$: take a bunch of $n/2$ parallel paths of length two.
  4. Formulas vs. Circuits: If the depth is restricted to $o(\log n)$ then STCON(n,k) requires even non-monotone(!) unbounded fanin formulas of size $n^{\Omega(\log k)}$ for all $k\leq \log\log n$. This was proved by Rossman, and separated for the first time bounded-depth circuits from formulas, because for such values of $k$, repeated squaring gives the desired small (even monotone) circuit of depth $2\log k\leq 2\log\log\log n=o(\log n)$.
  5. Directed vs. Undirected Connectivity: The directed reachability problem DSTCON(n) (where input graphs are directed) is a monotone projection of STCON(m) only if $m=n^{\Theta(\log n)}$. This was proved by Potechin, and separated monotone versions of L and NL.

Does anybody know some results more tightly related to the STCON(n,k) vs. STCON(n) question itself?


CORRECTION (Apr 9): Unfortunately, just taking $k$ copies of the input graph $G$ for STCON(n,k), only shows that STCON(n,k) is a monotone projection of DSTCON(kn), the directed (even acyclic) version of STCON. The difficult direction is to ensure that the modified graph $H=H_G$ has no s-t paths, when $G$ has s-t paths, but all they are longer than $k$. If $H$ is allowed to be directed, this is easy to ensure by arranging the copies of $G$ into $k$ layers, and drawing directed edges between layers according to $G$. But if the edges $H$ are required to be undirected, this simple layering trick won't work. So, I must refine my Question 2 as (cf. with the 5-th result by Potechin above):

Question 2': Is STCON(n,k) a monotone projection of DSTCON(m) for some $m < kn$?

Both answers would be interesting. If YES, this would show that layering is not the best way to "count". If NO, this would show that every monotone switching network for STCON(n,k) requires $kn$ nodes. (By the Bellman-Ford algorithm - which itself is just the "layering trick" in disguise - $kn$ nodes are also enough.)

$\endgroup$

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.