2
$\begingroup$

Let's say I have a graph $G=(V,E)$ where each vertex has an edge going both into and out of it (i.e. cyclic, akin to the kidney donor pair problem). Now suppose we have a capacity $u_{ij} = 1 \forall(i,j) \in E$ and supplies $b_i=0 \forall i\in V$. We also have some cost $c_{ij} \forall(i,j) \in E$.

The typical constraints for a MCF problem are not exceeding capacity and flow conservation: $$x_{ij} \leq u_{ij} \forall (i,j) \in E$$ $$\sum\limits_{ji}x_{ji}-\sum\limits_{ij}x_{ij}=b_i=0 \forall i \in V$$ Now suppose I want to model the following constraint using only input to the MCF algorithm. Let's say I only want exactly one unit or less of flow into and out of a given node, instead of merely satisfying flow conservation. I.e, I want to capture something stronger $(\dagger)$: $$\sum\limits_{ji}x_{ji} \leq 1 \hspace{5mm} \text{Flow into node i}$$ $$\sum\limits_{ij}x_{ij}\leq 1 \hspace{5mm} \text{Flow out of node i}$$ using only capacity and flow conservations constraints.

Subtracting the two constraints merely brings us back to flow conservation, so I believe additional structure is needed for the graph. So for a given node $i$, if we have more than one edge directed towards and out of the node, it becomes an issue as we could possibly send and receive two or more units. So we need to somehow "turn off" these additional edges once one edge is used. My intuition tells me we need to construct some dummy nodes that somehow remove all flow going out of node $i$ so that when we look at flow conservation, we only have flow into node $i$ which we can then be used to restrict only one flow of unit into the node. However, this would require also changing the supply to $b_i' = 1$ which does not seem right. I want to keep the original supplies intact. I am currently stuck on how dummy nodes could be used to capture $(\dagger)$ or if dummy nodes are even the correct approach here.

$\endgroup$
4
$\begingroup$

The transformation you want is called node splitting. Replace node $i$ with two nodes $i'$ and $i''$, where all incoming arcs to node $i$ instead arrive at node $i'$ and all outgoing arcs from node $i$ instead leave node $i''$. Also introduce a directed arc from $i'$ to $i''$ with capacity $1$.

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