<p>The problem is NP-hard on layered graphs. This can be seen by reduction from Exact Cover by 3-sets (X3C). Let $A_1,\ldots,A_m$ be subsets of $\{1,2,\ldots,3n\}$ with $\vert A_i\rvert=3$ for every $i$, the problem asks if there exists a set $I\subseteq\{1,2,\ldots,m\}$ of $\lvert I\rvert=n$ indices such that $\bigcup_{i\in I}A_i=\{1,2,\ldots,3n\}$. This can be reduced to the following instance of your problem. The node set is
$$V=\{s,t\}\cup\{v_i\ :\ i=1,2,\ldots,m\}\cup\{w_j\ :\ j=1,2,\ldots,3n\}.$$
There are the following arcs:</p>

<ul>
<li>an arc $(s,v_i)$ with capacity 3 for every $i\in\{1,2,\ldots,m\}$,</li>
<li>an arc $(v_i,w_j)$ with capacity 1 for every pair $(i,j)$ with $j\in A_i$</li>
<li>an arc $(w_j,t)$ with capacity 1 for every $j\in\{1,2,\dots,3n\}$.</li>
</ul>

<p>A flow of value $3n$ can be achieved using $4n$ nodes (not counting $s$ and $t$) if and only if the X3C-instance is a YES-instance. </p>

CC BY-SA 3.0
2013-10-19T00:50:15.877Z
Thanks for that answer Thomas. 

The reduction from X3C to my problem (or even a reduction from Set Cover) allows me to say that in a layered graph with $D$ layers and upto $K$ nodes per layer, the run-time dependence on $K$ has to be exponential (because if it were not exponential in $K$, then set cover would be solvable efficiently...). However, I am more interested in the case when $K$ is fixed while $D$ becomes large, i.e. what would be the dependence of the run-time on $D$? 

(Sorry for not mentioning this explicitly in the problem.)
rk2
CC BY-SA 3.0
2013-10-20T05:50:25.870Z
Not sure if useful but whenever the max flow $f^*$ is polynomial and $K$ is constant, the problem can be solved in poly time via dynamic programming. Define the subproblems parametrized by the considered first $i$ layers, the no of nodes $k$ included among the $i$ layers, and the flows passing through edges between layers $i$ and $i+1$. The no of such subproblems is at most ${f^*}^{K^2} KD$ and for each, one optimizes the max flow reaching sinks while satisfying the conditions. Each such optimization is poly time by iterating over smaller solutions and ways to include nodes and routing flow.
c.lorenz
CC BY-SA 3.0
2013-10-18T05:10:06.213Z
2013-10-18T05:10:06.213Z
Thomas Kalinowski
<p>In a standard Ford-Fulkerson setting (directed graph $G$ with a source $s$ and a sink $t$), consider the problem of achieving a given amount of flow using the <em>minimum number of nodes</em> in the graph.</p>

<p>The familiarity with the problem discussed here: <a href="https://cstheory.stackexchange.com/questions/7520/laying-paths-on-a-network-using-minimum-number-of-links-edges">Laying paths on a network using minimum number of links/edges</a> seems to suggest that this problem might also be NP-hard. I can split every node in $G$ into two nodes and add an edge of unit cost between them, and assign zero cost to all the original edges. Cap-SNDP (<a href="http://www.cis.upenn.edu/~sanjeev/papers/ipco11_capacitated.pdf" rel="nofollow noreferrer">http://www.cis.upenn.edu/~sanjeev/papers/ipco11_capacitated.pdf</a>) on this new graph is equivalent to finding the minimum number of nodes in $G$ required to support the desired flow. </p>

<p>1) Is this problem known to be NP-hard?</p>

<p>2) If I restrict attention to layered graphs, does it change anything about the complexity/approximability? (A layered graph is one in which all $s-t$ paths have the same number of edges.)</p>

<p>Thanks in advance.</p>

<graph-theory><graph-algorithms>
network flow using minimum number of nodes
rk2
# network flow using minimum number of nodes

(Asked by: username_0 on 2013-10-17)

In a standard Ford-Fulkerson setting (directed graph $G$ with a source $s$ and a sink $t$), consider the problem of achieving a given amount of flow using the *minimum number of nodes* in the graph.

The familiarity with the problem discussed here: [Laying paths on a network using minimum number of links/edges](https://cstheory.stackexchange.com/questions/7520/laying-paths-on-a-network-using-minimum-number-of-links-edges) seems to suggest that this problem might also be NP-hard. I can split every node in $G$ into two nodes and add an edge of unit cost between them, and assign zero cost to all the original edges. Cap-SNDP (<http://www.cis.upenn.edu/~sanjeev/papers/ipco11_capacitated.pdf>) on this new graph is equivalent to finding the minimum number of nodes in $G$ required to support the desired flow.

1) Is this problem known to be NP-hard?

2) If I restrict attention to layered graphs, does it change anything about the complexity/approximability? (A layered graph is one in which all $s-t$ paths have the same number of edges.)

Thanks in advance.

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

---

## 1 answers

### Answer by username_1 on 2013-10-18. Score: 4

The problem is NP-hard on layered graphs. This can be seen by reduction from Exact Cover by 3-sets (X3C). Let $A\_1,\ldots,A\_m$ be subsets of $\{1,2,\ldots,3n\}$ with $\vert A\_i\rvert=3$ for every $i$, the problem asks if there exists a set $I\subseteq\{1,2,\ldots,m\}$ of $\lvert I\rvert=n$ indices such that $\bigcup\_{i\in I}A\_i=\{1,2,\ldots,3n\}$. This can be reduced to the following instance of your problem. The node set is
$$V=\{s,t\}\cup\{v\_i\ :\ i=1,2,\ldots,m\}\cup\{w\_j\ :\ j=1,2,\ldots,3n\}.$$
There are the following arcs:

* an arc $(s,v\_i)$ with capacity 3 for every $i\in\{1,2,\ldots,m\}$,
* an arc $(v\_i,w\_j)$ with capacity 1 for every pair $(i,j)$ with $j\in A\_i$
* an arc $(w\_j,t)$ with capacity 1 for every $j\in\{1,2,\dots,3n\}$.

A flow of value $3n$ can be achieved using $4n$ nodes (not counting $s$ and $t$) if and only if the X3C-instance is a YES-instance.

> **Comments:**
> **username_0**: Thanks for that answer Thomas.   The reduction from X3C to my problem (or even a reduction from Set Cover) allows me to say that in a layered graph with $D$ layers and upto $K$ nodes per layer, the run-time dependence on $K$ has to be exponential (because if it were not exponential in $K$, then set cover would be solvable efficiently...). However, I am more interested in the case when $K$ is fixed while $D$ becomes large, i.e. what would be the dependence of the run-time on $D$?   (Sorry for not mentioning this explicitly in the problem.)  
> **username_2**: Not sure if useful but whenever the max flow $f^*$ is polynomial and $K$ is constant, the problem can be solved in poly time via dynamic programming. Define the subproblems parametrized by the considered first $i$ layers, the no of nodes $k$ included among the $i$ layers, and the flows passing through edges between layers $i$ and $i+1$. The no of such subproblems is at most ${f^*}^{K^2} KD$ and for each, one optimizes the max flow reaching sinks while satisfying the conditions. Each such optimization is poly time by iterating over smaller solutions and ways to include nodes and routing flow.  

---

