1
$\begingroup$

Here is the problem:

Input:

  • A series of source/sink nodes at fixed positions with given outwards/inwards flow

  • Edges are NOT specified. The edges can connect any nodes.

  • The total source and sink flow match

  • A concave cost function that gives a cost per edge in terms of flow capacity

Expected output:

  • The minimum costing graph (not necessarily fully connected) that connects all sources to sinks and permits the required flow, without creating extra nodes.

Therefore the network topology is unspecified and should be optimized.

Many thanks.

$\endgroup$
  • $\begingroup$ Would be accurate and concise to describe the problem as "minflow on complete graph with cost a concave function of flow for each edge"? $\endgroup$ – Apiwat Chantawibul Oct 23 '19 at 16:04
  • $\begingroup$ Indeed, this seems to be correct. $\endgroup$ – cvcs5 Oct 23 '19 at 16:40
0
$\begingroup$

Your problem is $\rm NP$-hard by a reduction from the minimum-weight Steiner tree problem.

Let $G=(V,E;w)$ be a graph with non-negative edge weights $w(e)$, $e \in E$, and let $S \subseteq V $ be a non-empty set of terminal vertices.

The vertex set in your problem will coincide with $V$. Choose the concave function $c_e(x)$ that describes the cost of sending $x$ units of flow across edge $e$ as $c_e(x) = w(e)$. Pick an arbitrary terminal $s \in S$ and make it a source with supply $|S|-1$. Make every vertex in $S \setminus \{ s \}$ a sink with demand $1$.

There is a Steiner tree $T$ of cost at most $k$ if and only if your problem admits a flow of cost at most $k$.

$\Rightarrow$) $s$ send one unit of flow to each vertex $v \in S \setminus \{ s \}$ using the unique path in $T$ between $s$ and $v$.

$\Leftarrow$) Consider the subgraph $H$ of $G$ induced by the set of edges traversed by non-zero flow. Since $H$ contains at least one path from $s$ to each vertex in $S \setminus \{ s \}$, it must have a connected component $C$ that spans all the vertices in $S$. Let $T$ be an arbitrary spanning tree of $C$. The cost of $T$ w.r.t. $w$ is exactly the contribution of the edges in $T$ to the cost of the flow. By our choice of the concave functions, this is upper bounded by the cost of the flow itself.

Notice that, by suitably subtracting epsilons from the cost functions, you can adapt this reduction to work for strictly concave functions. In this case it is convenient to relate a flow of cost at most $k$ to Steiner tree of cost at most $\lceil k \rceil$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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