3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 24, 2022 at 22:16
  • $\begingroup$ Added an example: additive gap can be bounded by the number of edges, but the ratio can be arbitrarily bad. $\endgroup$
    – Chao Xu
    Mar 25, 2022 at 7:25

2 Answers 2

5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

enter image description here

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

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$

$\endgroup$
0

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.