How to reduce $k$-oriented problem to max flow problem?

Question

Given an undirected graph $G$, how to reduce this problem :"Judge whether every edge of $G$ can be given a orientation such that for every vertex $v$ in $G$ has input-degree of at most $k$" to a max flow problem?

I tried the method in this link where input or output degree are the same because we can change all the orientation simultaneously. But the main distinction lies in "every vertex has at least output degrees" instead of "at most" and I havn't found how to modify this method.

Also post here: https://math.stackexchange.com/posts/4732656/

Answer 1

A similar solution to the one given here works here as well. The following is the reduction (non-highlighted statements are directly taken from Steven's answer):

Given $G=(V,E)$, create a directed bipartite graph $H=(V+E, F)$ where there is an edge $(v,e) \in F$ iff $v \in V$ is an endpoint of $e \in E$. All these edges have capacity $1$.

Augment $H$ as follows: add two additional vertices $s$ and $t$; for each $v \in V$ add an edge $(s,v)$ with capacity $k$; for each $e \in E$ add the edge $(e, t)$ with capacity $1$.

Compute a maximum flow $\phi$ from $s$ to $t$ in the augmented version of $H$. Your problem admits a solution if and only if the amount of flow $|\phi|$ is $|E|$. This ensures that all edges are oriented in the original graph.