3
$\begingroup$

There is a problem that is of great interest for communications and optics, but I do not know if there is an easy solution of it. We are looking for an oriented graph that goes from a node A (starting point) to a node B (ending point) that has a fixed number N different paths from A to B. Intermediate nodes that can only split or recombine two edges (so two input and two output nodes). What are the graphs that minimize the number of nodes met in all the N paths.

$\endgroup$
1
$\begingroup$

If I understand the problem properly, the answer should be $2 \log_2(n)$: make a graph with $\log_2(n) + 2$ layers, where the first layer is just $A$, the last layer is just $B$, and the intermediate layers have $2$ nodes each; we then put a directed edge from each node to the node(s) in the next layer. We then have $2^{\log_2(n)} = n$ paths from $A$ to $B$, and the union of these paths contains $2 \log_2(n)$ intermediate nodes.

Does this fit the constraints of your problem?

$\endgroup$
  • $\begingroup$ This only works when $n$ is a power of two. But you can get $O(\log n)$ for any $n$ by the same idea: make a graph with $\lfloor n/2\rfloor$ paths from its source to its destination, add two paths to a new destination to double the number of paths, and then add one more path if $n$ is odd. $\endgroup$ – David Eppstein Nov 8 '16 at 22:13
  • 4
    $\begingroup$ You can do better. E.g., use nodes $\{1,2,\ldots,k\}$, and edges $\{(1,2), (2,3), \ldots, (k-1, k)\} \cup \{(1,3), (2, 4), \ldots, (k-2,k)\}$. Then the number of paths grows like the $k$th Fibonacci number. So $n\approx 1.62^k$, i.e., $k \approx 1.44 \log_2 n$, I think. Not sure if this is optimum, though. By a straightforward counting argument you can't do better than $\log_2 n$. $\endgroup$ – Neal Young Nov 9 '16 at 2:23
  • 1
    $\begingroup$ Assuming the graph has to be a DAG, perhaps a proof by induction shows you can't do better than the Fibonacci strategy. (You could imagine the problem allows the graph not to be a DAG, but only counts simple paths.) $\endgroup$ – Neal Young Nov 9 '16 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.