<p>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.</p>

<p>Does this fit the constraints of your problem?</p>

CC BY-SA 3.0
2016-11-08T22:13:12.420Z
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.
David Eppstein
CC BY-SA 3.0
2016-11-09T02:23:38.030Z
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$.
Neal Young
CC BY-SA 3.0
2016-11-09T02:53:31.257Z
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.)
Neal Young
CC BY-SA 3.0
2016-10-09T19:05:25.233Z
2016-10-09T19:05:25.233Z
GMB
<p>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.</p>

<graph-theory><graph-algorithms>
Finding a graph that minimizes the number of nodes for a given number of paths
Gipfeli
# Finding a graph that minimizes the number of nodes for a given number of paths

(Asked by: username_0 on 2016-10-09)

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.

**Tags:** graph-theory, graph-algorithms

---

## 1 answers

### Answer by username_1 on 2016-10-09. Score: 1

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?

> **Comments:**
> **username_2**: 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.  
> **username_3**: 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$.  
> **username_3**: 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.)  

---

