# Red-blue cut in digraphs

::: {.problem #problem-red-blue-cut title="Red-blue cut in digraphs"}
Given a finite digraph $G=(V,E)$ with each arc colored red or blue, and binary-encoded nonnegative integers $r$ and $b$, decide whether some $\emptyset\subsetneq S\subsetneq V$ has at most $r$ red arcs and at most $b$ blue arcs leaving it.
:::

::: {.theorem #thm:red-blue-cut-complexity title="Complexity"}
The red-blue cut problem is NP-complete, even when the input digraph has no loops, has at most one arc for each ordered pair of distinct vertices, and satisfies $r=b$.
:::

::: {.proof}
The problem belongs to NP because a proposed set $S$ can be checked for being nonempty and proper before scanning the arcs and counting the outgoing arcs of each color.

For NP-hardness, reduce from Unweighted Minimum Bisection, which is NP-complete by Garey et al., [“Some Simplified NP-Complete Graph Problems”](https://doi.org/10.1016/0304-3975%2876%2990059-1). Let $H=(U,A)$ be a simple undirected graph with $n=|U|=2k\ge2$ vertices and $m=|A|$ edges, and let $K$ be the requested upper bound on the number of edges crossing a bisection. Replace $K$ by $\min\{K,m\}$. This preserves the answer because every bisection crosses at most $m$ edges, and it ensures that the construction remains polynomial when the original threshold is encoded in binary. Define

$$
M:=K+1,\qquad T:=Mk+K,\qquad F:=T+1,\qquad L:=T+2,
$$

and set the target budgets to $r=b=T$.

Introduce logical vertices $Q:=U\mathbin{\dot\cup}\{s,t\}$. Replace every $p\in Q$ by a block $B_p$ of $L$ vertices, and add every red arc between distinct vertices of the same block. Add the following cross-block tokens:

1. For every $v\in U$, add $M$ red tokens from $v$ to $t$.
2. For every $v\in U$, add $M$ blue tokens from $s$ to $v$.
3. For every $v\in U$, add $F$ red tokens from $v$ to $s$ and $F$ red tokens from $t$ to $v$.
4. For every edge $\{u,v\}\in A$, add one red and one blue token in each direction between $u$ and $v$.

These tokens can be realized without loops or parallel arcs. For each ordered pair of distinct logical vertices $p,q$, index all tokens from $p$ to $q$, across both colors, by $j=0,\ldots,d_{p,q}-1$. The number $d_{p,q}$ is $0$, $M$, $F$, or $2$, and each of these is smaller than $L^2$. Realize token $j$ as the arc

$$
\left(p,1+\left\lfloor\frac jL\right\rfloor\right)\longrightarrow\left(q,1+(j\bmod L)\right)
$$

with the token's color. The quotient-remainder map is injective for $0\le j<L^2$. Tokens with different logical endpoints lie between different ordered pairs of blocks, and cross-block arcs cannot coincide with internal arcs. The resulting digraph is therefore simple and loopless.

Let $S$ satisfy both budgets. It cannot split a block. If $a:=|S\cap B_p|$ lies between $1$ and $L-1$, then the internal red arcs of $B_p$ contribute

$$
a(L-a)\ge L-1=T+1
$$

arcs leaving $S$, which exceeds the red budget. Hence $S$ is a union of whole blocks. Let $P:=\{p\in Q:B_p\subseteq S\}$. If $s\notin P$, then no vertex $v\in U$ can belong to $P$, because the $F=T+1$ red tokens $v\to s$ would leave $S$. Nonemptiness would then force $t\in P$, but the $F$ tokens $t\to v$ would leave $S$ for every $v\in U$. Thus $s\in P$. If $t\in P$, properness leaves some $v\in U$ outside $P$, and the $F$ tokens $t\to v$ again exceed the red budget. Thus $t\notin P$.

Define $X:=P\cap U$, let $x:=|X|$, and let $c$ be the number of edges of $H$ with exactly one endpoint in $X$. No forcing token leaves $S$. The tokens $v\to t$ contribute $Mx$ red arcs, the tokens $s\to v$ contribute $M(n-x)$ blue arcs, and each source edge crossing $X$ contributes exactly one outgoing token of each color. The two color counts are therefore

$$
R(S)=Mx+c,\qquad B(S)=M(n-x)+c.
$$

If $x\ge k+1$, then $R(S)\ge M(k+1)>Mk+K=T$. If $x\le k-1$, then $B(S)\ge M(k+1)>T$. Every feasible shore therefore has $x=k$, after which both budget inequalities are equivalent to $c\le K$.

If the source instance has a bisection $X$ with $c\le K$, then $S:=B_s\cup\bigcup_{v\in X}B_v$ is nonempty and proper and has $R(S)=B(S)=Mk+c\le T$. Conversely, every feasible shore yields a set $X$ with $|X|=k$ and $c\le K$. The reduction preserves the answer.

After normalization, $K\le m=O(n^2)$, so $L=O(n^3)$. The target has $(n+2)L=O(n^4)$ vertices and

$$
(n+2)L(L-1)+2nM+2nF+4m=O(n^7)
$$

arcs. The token assignment is explicit, and the target threshold has polynomial bit length. The reduction runs in polynomial time.
:::