<p>We can construct a widget for an all-or-nothing flow of capacity 4 from vertex s to t using the widget below. The stars (*) indicate even flows. By recursively applying similar widgets one can emulate all-or-nothing flows of any small size, so we can reduce the all-or-nothing flow problem to it, which we know is NP-hard (<a href="https://cs.stackexchange.com/a/114903/28999">https://cs.stackexchange.com/a/114903/28999</a>).</p>
<p><a href="https://i.sstatic.net/6DCG4.png" rel="noreferrer"><img src="https://i.sstatic.net/6DCG4.png" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2022-03-26T14:50:25.950Z
2022-03-26T14:50:25.950Z
Albert Hendriks
<p><strong>Theorem 1.</strong> <em>The problem is NP-hard.</em></p>
<p><em>Proof sketch.</em> By reduction from maximum independent set in cubic graphs (which <a href="https://cstheory.stackexchange.com/questions/46633/is-the-maximum-independent-set-in-cubic-planar-graphs-np-complete">is NP-hard</a>).</p>
<p>Given a cubic graph <span class="math-container">$G=(V, E)$</span>, the reduction outputs a flow network as follows.</p>
<p>For every vertex <span class="math-container">$v\in V$</span>, build the following gadget <span class="math-container">$g_v$</span>:</p>
<p><a href="https://i.sstatic.net/dUrkZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/dUrkZ.png" alt="enter image description here" /></a></p>
<p>Each edge in the bottom and top layers of <span class="math-container">$g_v$</span> has capacity 2 with the parity restriction that its flow be even, so it must have flow 0 or 2. Each edge in the middle layer has capacity 1.  Note that *in any feasible integer flow (with the parity restriction), either all edges in <span class="math-container">$g_v$</span> are saturated, or all edges in <span class="math-container">$g_v$</span> have zero flow.</p>
<p>Now, for each edge <span class="math-container">$(u, w)$</span> in <span class="math-container">$G$</span>, choose unique vertices <span class="math-container">$u_1$</span> and <span class="math-container">$w_1$</span> in the top layer of <span class="math-container">$g_u$</span> and <span class="math-container">$g_w$</span>, respectively, and build the following NAND gadget <span class="math-container">$g_{uw}$</span> for edge <span class="math-container">$(u, w)$</span>:</p>
<p><a href="https://i.sstatic.net/5jKh9m.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5jKh9m.png" alt="enter image description here" /></a></p>
<p>The gadget has new edges out of <span class="math-container">$u_1$</span> and <span class="math-container">$w_1$</span> going to a new middle vertex, and a new edge out of the new middle vertex into a new top vertex.  All three new edges have capacity 2.</p>
<p>Each vertex <span class="math-container">$u$</span> in <span class="math-container">$G$</span> has degree three, so each of the three top nodes in <span class="math-container">$g_u$</span> is connected to exactly one edge gadget <span class="math-container">$g_{uw}$</span> for some <span class="math-container">$w$</span>.</p>
<p>Now introduce a source <span class="math-container">$s$</span> with an edge to each bottom node of each vertex gadget, and a sink <span class="math-container">$t$</span> with an edge from each top node of each edge gadget.  Give all the edges from <span class="math-container">$s$</span> and to <span class="math-container">$t$</span> capacity 2.</p>
<p>Now the feasible (parity-respecting) flows in this flow network correspond bijectively to independent sets in <span class="math-container">$G$</span>, and this correspondence preserves size, in that the value of the flow is six times the size of its corresponding independent set. <span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2022-03-26T14:32:15.217Z
2022-03-27T16:59:05.660Z
2022-03-27T16:59:05.660Z
Neal Young
<p>Consider the maximum integral flow problem on a directed graph <span class="math-container">$G=(V,E)$</span> with integral capacities <span class="math-container">$c:E\to \mathbb{N}$</span>. We have an additional constraint that for the set of edges in <span class="math-container">$F\subseteq E$</span>, the flow value has to be even. Such flow is called <span class="math-container">$F$</span>-even max-flow.</p>
<p>Is finding the maximum <span class="math-container">$F$</span>-even max-flow NP-hard?</p>
<p><strong>The gap between <span class="math-container">$F$</span>-even max-flow and max-flow</strong></p>
<p>Consider 2 edges <span class="math-container">$(s,v)$</span>,<span class="math-container">$(v,t)$</span>. where edge <span class="math-container">$(s,v)$</span> has capacity <span class="math-container">$2$</span>, and <span class="math-container">$F=\{(s,v)\}$</span>. <span class="math-container">$(v,t)$</span> has capacity 1. The max flow is 1 and <span class="math-container">$F$</span>-even max-flow is 0. One can use this to construct larger examples.</p>
<p>The difference between <span class="math-container">$F$</span>-even max-flow and max-flow is bounded by <span class="math-container">$|E|$</span>. Setting <span class="math-container">$c'(e) = \lfloor c(e)/2 \rfloor$</span>, we can compute a maximum flow with respect to <span class="math-container">$c'$</span>. We can scale it to obtain a <span class="math-container">$E$</span>-even max-flow with respect to <span class="math-container">$c$</span>. The difference with the max-flow with respect to <span class="math-container">$c$</span> is at most <span class="math-container">$|E|$</span>.</p>
<p>Maybe one can show it is bounded by <span class="math-container">$|F|$</span>.</p>

CC BY-SA 4.0
2022-03-24T22:16:32.137Z
Do you have examples which show that the maxflow with the additional constraint would be substantially reduced from the unconstrained setting? Just curious to see if that can help figure out hardness.
Chandra Chekuri
CC BY-SA 4.0
2022-03-25T07:25:50.550Z
Added an example: additive gap can be bounded by the number of edges, but the ratio can be arbitrarily bad.
Chao Xu
<max-flow><flow-problems>
Maximum flow with parity requirement on certain edges
Chao Xu
# Maximum flow with parity requirement on certain edges

(Asked by: username_0 on 2022-03-24)

Consider the maximum integral flow problem on a directed graph $G=(V,E)$ with integral capacities $c:E\to \mathbb{N}$. We have an additional constraint that for the set of edges in $F\subseteq E$, the flow value has to be even. Such flow is called $F$-even max-flow.

Is finding the maximum $F$-even max-flow NP-hard?

**The gap between $F$-even max-flow and max-flow**

Consider 2 edges $(s,v)$,$(v,t)$. where edge $(s,v)$ has capacity $2$, and $F=\{(s,v)\}$. $(v,t)$ has capacity 1. The max flow is 1 and $F$-even max-flow is 0. One can use this to construct larger examples.

The difference between $F$-even max-flow and max-flow is bounded by $|E|$. Setting $c'(e) = \lfloor c(e)/2 \rfloor$, we can compute a maximum flow with respect to $c'$. We can scale it to obtain a $E$-even max-flow with respect to $c$. The difference with the max-flow with respect to $c$ is at most $|E|$.

Maybe one can show it is bounded by $|F|$.

**Tags:** max-flow, flow-problems
> **Comments:**
> **username_1**: Do you have examples which show that the maxflow with the additional constraint would be substantially reduced from the unconstrained setting? Just curious to see if that can help figure out hardness.  
> **username_0**: Added an example: additive gap can be bounded by the number of edges, but the ratio can be arbitrarily bad.  

---

## 2 answers

### Answer by username_2 on 2022-03-26. Score: 5 | Accepted answer

We can construct a widget for an all-or-nothing flow of capacity 4 from vertex s to t using the widget below. The stars (\*) indicate even flows. By recursively applying similar widgets one can emulate all-or-nothing flows of any small size, so we can reduce the all-or-nothing flow problem to it, which we know is NP-hard (<https://cs.stackexchange.com/a/114903/28999>).

[![enter image description here](https://i.sstatic.net/6DCG4.png)](https://i.sstatic.net/6DCG4.png)


---

### Answer by username_3 on 2022-03-26. Score: 2

**Theorem 1.** *The problem is NP-hard.*

*Proof sketch.* By reduction from maximum independent set in cubic graphs (which [is NP-hard](https://cstheory.stackexchange.com/questions/46633/is-the-maximum-independent-set-in-cubic-planar-graphs-np-complete)).

Given a cubic graph $G=(V, E)$, the reduction outputs a flow network as follows.

For every vertex $v\in V$, build the following gadget $g\_v$:

[![enter image description here](https://i.sstatic.net/dUrkZ.png)](https://i.sstatic.net/dUrkZ.png)

Each edge in the bottom and top layers of $g\_v$ has capacity 2 with the parity restriction that its flow be even, so it must have flow 0 or 2. Each edge in the middle layer has capacity 1. Note that \*in any feasible integer flow (with the parity restriction), either all edges in $g\_v$ are saturated, or all edges in $g\_v$ have zero flow.

Now, for each edge $(u, w)$ in $G$, choose unique vertices $u\_1$ and $w\_1$ in the top layer of $g\_u$ and $g\_w$, respectively, and build the following NAND gadget $g\_{uw}$ for edge $(u, w)$:

[![enter image description here](https://i.sstatic.net/5jKh9m.png)](https://i.sstatic.net/5jKh9m.png)

The gadget has new edges out of $u\_1$ and $w\_1$ going to a new middle vertex, and a new edge out of the new middle vertex into a new top vertex. All three new edges have capacity 2.

Each vertex $u$ in $G$ has degree three, so each of the three top nodes in $g\_u$ is connected to exactly one edge gadget $g\_{uw}$ for some $w$.

Now introduce a source $s$ with an edge to each bottom node of each vertex gadget, and a sink $t$ with an edge from each top node of each edge gadget. Give all the edges from $s$ and to $t$ capacity 2.

Now the feasible (parity-respecting) flows in this flow network correspond bijectively to independent sets in $G$, and this correspondence preserves size, in that the value of the flow is six times the size of its corresponding independent set. $~~~~\Box$


---

