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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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?
-
$\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$ Commented Nov 8, 2016 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$ Commented Nov 9, 2016 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$ Commented Nov 9, 2016 at 2:53