# Flow with edge-weight restrictions

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

• 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. Jan 31, 2022 at 19:05

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.
• 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.) Feb 1, 2022 at 17:07
• @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.