Maximum flow with parity requirement on certain edges

Question

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

Answer 1

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

Answer 2

Theorem 1. The problem is NP-hard.

Proof sketch. By reduction from maximum independent set in cubic graphs (which is NP-hard).

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$:

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)$:

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$