NP-completitud del problema de grafos planos no dirigidos

Se puede resolver en tiempo polinomial reduciéndolo al problema de flujo máximo , por lo que es poco probable que sea NP-completo.

Está claro que la suma de todos los números debe ser igual al número de aristas. Si es así, la reducción funciona de la siguiente manera.

Por cada vértice$v$y borde$e$del gráfico original tendremos vértice en la red. También agregar fuente$s$y hundirse$t$.

Los bordes en la red son los siguientes:

• para vértice$v$con número$n$añadir borde$s \to v$con capacidad$n$
• para el borde$e = (v_1, v_2)$agregar bordes$v_1 \to e$,$v_2 \to e$,$e \to t$con capacidades$1$

Ahora, si tenemos un flujo entero con un valor igual al número de aristas (para que haya flujo desde cada arista), podemos asignar direcciones: para arista$e = (v_1, v_2)$hay flujo de valor$1$a$e$desde cualquiera$v_1$o$v_2$- borde directo desde$v_1$a$v_2$en el primer caso, y de$v_2$a$v_1$en el posterior. De esta manera, cada borde está dirigido y cada vértice tiene un número de bordes salientes igual a su número.

De manera similar, si tenemos una dirección de aristas, podemos crear un flujo con un valor igual al número de aristas.

Por lo tanto, el gráfico original se puede dirigir si y solo si hay un flujo con un valor igual al número de aristas. Como el problema de flujo máximo se puede resolver en tiempo polinomial, también puede ser un problema original.