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

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.

  • 1
    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 Oct 19 '13 at 0:50
  • 1
    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 Oct 20 '13 at 5:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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