3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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.) $\endgroup$
    – rk2
    Commented Oct 19, 2013 at 0:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – c.lorenz
    Commented Oct 20, 2013 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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