NP-completeness of undirected planar graph problem

Question

I want to know whether a certain graph problem is NP-complete or not. The problem is as follows.

Given an undirected planar graph with in every vertex a number. Can you give every edge a direction such that the outdegree of every vertex is equal to the corresponding number?

Does anyone have an idea whether this problem is NP-complete, or know a related problem?

Answer 1

It can be solved in polynomial time by reducing it to maximum flow problem, so it's unlikely to be NP-complete.

It's clear that sum of all numbers should be equal to number of edges. It it's so, the reduction works as follow.

For each vertex $v$ and edge $e$ from original graph we will have vertex in network. Also add source $s$ and sink $t$.

Edges in network are as follow:

• for vertex $v$ with number $n$ add edge $s \to v$ with capacity $n$
• for edge $e = (v_1, v_2)$ add edges $v_1 \to e$, $v_2 \to e$, $e \to t$ with capacities $1$

Now, if we have integer flow with value equal to number of edges (so that there is flow from every edge), we can assign directions: for edge $e = (v_1, v_2)$ there is flow of value $1$ to $e$ from either $v_1$ or $v_2$ - direct edge from $v_1$ to $v_2$ in the former case, and from $v_2$ to $v_1$ in the later. This way every edge is directed, and each vertex has number of outgoing edges equal to it's number.

Similarly, if we have a direction of edges, we can create flow with value equal to number of edges.

Thus, original graph can be directed iff there is a flow with value equal to number of edges. As max flow problem can be solved in polynomial time, so can be original problem.