Problema de realización de digrafos

El problema de realización de digrafos es un problema de decisión en la teoría de grafos . Dados pares de enteros no negativos${\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}$, el problema pregunta si existe un grafo dirigido simple etiquetado tal que cada vértice${\displaystyle v_{i}}$tiene grado de entrada${\displaystyle a_{i}}$y grado de salida${\displaystyle b_{i}}$.

El problema pertenece a la clase de complejidad P. Se conocen dos algoritmos para demostrarlo. El primer enfoque lo proporcionan los algoritmos de Kleitman-Wang, que construyen una solución especial mediante un algoritmo recursivo . El segundo es una caracterización mediante el teorema de Fulkerson-Chen-Anstee , es decir, hay que validar la corrección de${\displaystyle n}$desigualdades.

El problema también puede plantearse en términos de matrices binarias . La conexión puede verse si uno se da cuenta de que cada grafo dirigido tiene una matriz de adyacencia donde las sumas de las columnas y las sumas de las filas corresponden a${\displaystyle (a_{1},\cdots ,a_{n})}$y${\displaystyle (b_{1},\ldots ,b_{n})}$Nótese que la diagonal de la matriz solo contiene ceros. El problema se suele representar mediante matrices binarias (0-1) para sumas de filas y columnas dadas . En la literatura clásica, el problema se planteaba a veces en el contexto de tablas de contingencia mediante tablas de contingencia con marginales dadas .

Problemas similares describen las secuencias de grados de grafos simples , grafos dirigidos simples con bucles y grafos bipartitos simples . El primer problema es el llamado problema de realización de grafos . El segundo y el tercero son equivalentes y se conocen como el problema de realización bipartita . Chen (1966) da una caracterización para multigrafos dirigidos con un número acotado de arcos paralelos y bucles a una secuencia de grados dada . La restricción adicional de la aciclicidad del grafo dirigido se conoce como realización de DAG . Nichterlein y Hartung (2012) demostraron la NP-completitud de este problema. Berger y Müller-Hannemann (2011) mostraron que la clase de secuencias opuestas está en P. El problema del muestreo uniforme de un grafo dirigido a una secuencia de grados fija es construir una solución para el problema de realización de digrafos con la restricción adicional de que cada solución llegue con la misma probabilidad. Catherine Greenhill ( 2011 ) demostró que este problema se encuentra en FPTAS para secuencias regulares. El problema general aún no se ha resuelto. 

• Chen, Wai-Kai ( 1966), "Sobre la realización de un ( p , s )-dígrafo con grados prescritos", Journal of the Franklin Institute , 103 : 406–422
• Nichterlein, André; Hartung, Sepp (2012), "NP-Dardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs", Journal of the Franklin Institute , 7318 : 283– 292
• Berger, Annabell; Müller-Hannemann, Matthias ( 2011), "Realizaciones DAG de secuencias de grados dirigidas", Actas de la 18.ª Conferencia Internacional sobre Fundamentos de la Teoría de la Computación : 264–275
• Greenhill, Catherine (2011), "Una cota polinómica para el tiempo de mezcla de una cadena de Markov para el muestreo de grafos dirigidos regulares", Electronic Journal of Combinatorics , 18