4
$\begingroup$

I am interested in the following. Let the inputs of the circuit correspond to the arcs of a directed graph. The circuit has to output 1 iff there is a directed path from a given node S to a given node T such that all arcs on that path have input value 1.

I can construct Boolean circuits that have size linear in nm where n is the number of vertices in the graph and m is the number of arcs. I would like to know if smaller circuits are possible. Especially, circuits that are linear in n+m.

$\endgroup$
  • 1
    $\begingroup$ Bad news: no lower bound of the form $\Omega(nm)$ is known, even for <i>monotone</i> circuits. The upper bound $O(nm)$ comes directly from Bellman-Ford DP algorithm. Actually, Floyd-Warshall gives a monotone circuit of size $O(n^3)$ even for the "all pairs connectivity" function, where existence of paths between all pairs $s$ and $t$ are computed (so, we already need $\Omega(n^2)$ output gates!). Here $\Omega(n^3)$ lower bound is already known (even for graphs with two layers); see e.g. Sect. 6.8 of Wegener's book. $\endgroup$ – Stasys Dec 22 '14 at 11:26

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.