2
$\begingroup$

I am given a graph $G=(V,E)$ undirected and two vertices, the source vertex $s$ and the target vertex $t$. Additionally, each edge comes with a capacity $c(e)$ (non-negative) and a set of weight functions $w_1(e),...,w_k(e)$. To simplify things, assume these weight functions are non-negative as well. I am also given a set of upper bounds $l_1 ,...,l_k$.

The weight of a set of edges under any $w_i$ is additive. Denote $\tilde{E}$ as the set of edges (from the original graph) with positive flow (not back edges with the reverse flow, and not edges with a flow of zero). I would like to find the maximal flow between $s$ and $t$ such that $w_i (\tilde{E} ) \leq l_i$ for all indices $i$.

In other words, I am trying to find a flow under constraints for the edges that are being used.

I'm assuming this problem, as described, might be too hard to tackle. In this case, some assumptions can be made:

  1. $c(e) = 1$ for all edges.
  2. The goal is to find a flow $|f| > 1$, but it does not have to be maximal, only non-trivial.

If this is still too hard, we can assume that $k=1$ and, for an edge, there is only the capacity and the weight. (I'm interested in the case of several weight functions, but if that approach is too hard, also a single weight function, and perhaps that idea can be generalized).

$\endgroup$
1
  • $\begingroup$ Since the problem is similar to the minimum cost flow problem. I tried to design a linear program for your problem. I have trouble imposing the constraint that a variable $y(e)$ is $1$ if flow through $e$ is non-zero; otherwise $y(e) = 0$. Can we write this constraint as a linear program? then, we are done. $\endgroup$ Jan 31, 2022 at 19:05

1 Answer 1

2
$\begingroup$

If $k=1$ and $c(e)=1$ for all edges $e$, then this looks equivalent to the minimum cost flow problem -- specifically, to finding an integral minimum cost flow. I believe combinatorial methods for the minimum cost flow problem are guaranteed to output an integral solution (if one exists).

If $k>1$, this reminds me of multi commodity flow which is NP-hard. You might check whether the proof of NP-hardness for (integral) multi commodity flow can be adjusted to apply to your problem as well.

If I had to solve it in practice, I would start by formulating it as an integer linear program and applying an ILP solver. In particular, you could introduce a zero-or-one variable $x_e$ for each edge $e$, with intention that if $x_e=0$ then the flow through $e$ is 0, and if $x_e=1$ then the flow through $e$ is non-zero. Assuming you are interested in integral flows (which you didn't actually state), then you can enforce this with the linear inequalities $f_e \ge x_e$ and $f_e \le M x_e$ where $M$ is a sufficiently large constant. Then add the flow conservation equations and minimize your objective function (which is a linear function of the $x$'s), and you should be good to go.

$\endgroup$
2
  • $\begingroup$ Hi D.W., in the minimum cost flow problems, we often take take cost due to an edge $(u,v)$ as $f(u,v) \cdot a(u,v)$, where $f(u,v)$ is the flow through $(u,v)$ and $a(u,v)$ is some constant. However, in this problem, the cost is defined as $a(u,v)$ if the flow through $(u,v)$ is non-zero; otherwise cost is $0$. By $a(u,v)$, I mean $w_{i}(u,v)$ as per this question. So, I am not sure, if such a constraint can be modeled. (Note: I am assuming fractional flow.) $\endgroup$ Feb 1, 2022 at 17:07
  • 1
    $\begingroup$ @InuyashaYagami, yes, I know. If $c(e)=1$ and the flow is integral, then the flow must be either 0 or 1, hence the equivalence to minimum cost flow in that special case. My answer assumes integral flow, as mentioned in the first sentence of my answer. $\endgroup$
    – D.W.
    Feb 1, 2022 at 18:57

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.