Conjunto de arco de retroalimentación

Aristas que tocan todos los ciclos en un gráfico

Partición de un gráfico dirigido en un conjunto de arcos de retroalimentación mínimos (bordes discontinuos rojos) y un subgráfico acíclico máximo (bordes sólidos azules)

En teoría de grafos y algoritmos de grafos , un conjunto de arcos de retroalimentación o un conjunto de aristas de retroalimentación en un grafo dirigido es un subconjunto de las aristas del grafo que contiene al menos una arista de cada ciclo del grafo. Eliminar estas aristas del grafo rompe todos los ciclos, produciendo un subgrafo acíclico del grafo dado, a menudo llamado grafo acíclico dirigido . Un conjunto de arcos de retroalimentación con la menor cantidad posible de aristas es un conjunto de arcos de retroalimentación mínimo y su eliminación deja un subgrafo acíclico máximo ; también se utilizan versiones ponderadas de estos problemas de optimización . Si un conjunto de arcos de retroalimentación es mínimo, lo que significa que eliminar cualquier arista de él produce un subconjunto que no es un conjunto de arcos de retroalimentación, entonces tiene una propiedad adicional: invertir todas sus aristas, en lugar de eliminarlas, produce un grafo acíclico dirigido.

Los conjuntos de arcos de retroalimentación tienen aplicaciones en el análisis de circuitos, la ingeniería química , la resolución de puntos muertos , la votación clasificada , la clasificación de competidores en eventos deportivos, la psicología matemática , la etología y el dibujo de gráficos . Encontrar conjuntos de arcos de retroalimentación mínimos y subgrafos acíclicos máximos es NP-difícil ; se puede resolver exactamente en tiempo exponencial o en tiempo manejable con parámetros fijos . En tiempo polinomial , el conjunto de arcos de retroalimentación mínimo se puede aproximar dentro de una razón de aproximación polilogarítmica , y los subgrafos acíclicos máximos se pueden aproximar dentro de un factor constante. Ambos son difíciles de aproximar más cerca que algún factor constante, un resultado de inaproximabilidad que se puede fortalecer bajo la conjetura de juegos únicos . Para los gráficos de torneos , el conjunto de arcos de retroalimentación mínimo se puede aproximar con mayor precisión, y para los gráficos planares ambos problemas se pueden resolver exactamente en tiempo polinomial.

Un problema estrechamente relacionado, el conjunto de vértices de retroalimentación , es un conjunto de vértices que contiene al menos un vértice de cada ciclo en un grafo dirigido o no dirigido. En los grafos no dirigidos , los árboles de expansión son los subgrafos acíclicos más grandes, y la cantidad de aristas eliminadas para formar un árbol de expansión es el rango del circuito .

Aplicaciones

Puntuaciones del vóleibol de playa masculino en los Juegos Olímpicos de 2016 , grupo F, y la clasificación de mínima sorpresa para estas puntuaciones. Las flechas apuntan del perdedor al ganador de cada partido, y son de color azul cuando el resultado es consistente con la clasificación y rojo para una sorpresa, un resultado inconsistente con la clasificación. Con esta clasificación, solo un partido es una sorpresa, aquel en el que EE. UU. venció a QAT. La clasificación real utilizada en los Juegos Olímpicos difería al colocar a ESP por delante de QAT en la proporción de sets, lo que provocó que su partido se clasificara como otra sorpresa. ^[1]

Varios problemas que implican la búsqueda de clasificaciones u ordenamientos se pueden resolver encontrando un conjunto de arcos de retroalimentación en un grafo de torneo , un grafo dirigido con una arista entre cada par de vértices. Al invertir las aristas del conjunto de arcos de retroalimentación se produce un grafo acíclico dirigido cuyo orden topológico único se puede utilizar como la clasificación deseada. Las aplicaciones de este método incluyen las siguientes:

• En las competiciones deportivas con sistema de todos contra todos , los resultados de cada juego se pueden registrar dirigiendo una ventaja del perdedor al ganador de cada juego. Encontrar un arco de retroalimentación mínimo establecido en el gráfico resultante, invertir sus aristas y ordenar topológicamente, produce una clasificación de todos los competidores. Entre todas las diferentes formas de elegir una clasificación, minimiza el número total de sorpresas, juegos en los que un competidor de menor clasificación vence a un competidor de mayor clasificación. ^{[2] [3] [4]} Muchos deportes utilizan métodos más simples para los sistemas de clasificación de torneos grupales basados ​​en los puntos otorgados por cada juego; ^[5] estos métodos pueden proporcionar una aproximación constante a la clasificación de sorpresa mínima. ^[6]
• En primatología y, más generalmente, en etología , las jerarquías de dominancia se determinan a menudo mediante la búsqueda de un orden con la menor cantidad de inversiones en el comportamiento de dominancia observado, otra forma del problema del arco de retroalimentación mínimo. ^{[7] [8] [9]}
• En psicología matemática , resulta de interés determinar la clasificación de los sujetos de conjuntos de objetos según un criterio dado, como su preferencia o su percepción del tamaño, basándose en comparaciones por pares entre todos los pares de objetos. El arco de retroalimentación mínimo establecido en un gráfico de torneo proporciona una clasificación que está en desacuerdo con la menor cantidad posible de resultados por pares. ^{[2] [10]} Alternativamente, si estas comparaciones dan como resultado probabilidades independientes para cada ordenamiento por pares, entonces la estimación de máxima verosimilitud de la clasificación general se puede obtener convirtiendo estas probabilidades en log-verosimilitudes y encontrando un arco de retroalimentación de peso mínimo establecido en el torneo resultante. ^{[2] [3]}
• El mismo ordenamiento de máxima verosimilitud se puede utilizar para la seriación , el problema en estadística y análisis exploratorio de datos de organizar elementos en un ordenamiento lineal, en casos donde hay datos disponibles que proporcionan comparaciones por pares entre los elementos. ^{[3] [11] [12]}
• En la votación por orden de preferencia , el método Kemeny-Young puede describirse como la búsqueda de un orden que minimice la suma, sobre pares de candidatos, del número de votantes que prefieren el orden opuesto para ese par. ^[13] Esto puede formularse y resolverse como un problema de arco de retroalimentación de peso mínimo, en el que los vértices representan candidatos, las aristas están dirigidas a representar al ganador de cada contienda cara a cara, y el costo de cada arista representa el número de votantes que se sentirían infelices si se le diera una clasificación más alta al perdedor de la contienda cara a cara. ^[14]

Otra aplicación temprana de los conjuntos de arcos de retroalimentación se refería al diseño de circuitos lógicos secuenciales , en los que las señales pueden propagarse en ciclos a través del circuito en lugar de progresar siempre desde las entradas a las salidas. En tales circuitos, un conjunto de arcos de retroalimentación mínimo caracteriza el número de puntos en los que es necesaria la amplificación para permitir que las señales se propaguen sin pérdida de información. ^[15] En circuitos sincrónicos hechos a partir de componentes asincrónicos, la sincronización se puede lograr colocando puertas sincronizadas en los bordes de un conjunto de arcos de retroalimentación. ^[16] Además, cortar un circuito en un conjunto de arcos de retroalimentación reduce el circuito restante a lógica combinacional , simplificando su análisis, y el tamaño del conjunto de arcos de retroalimentación controla cuánto análisis adicional se necesita para comprender el comportamiento del circuito a lo largo del corte. ^[15] De manera similar, en el diagrama de flujo de procesos en ingeniería química , romper los bordes de un diagrama de flujo de procesos en un conjunto de arcos de retroalimentación y adivinar o probar todas las posibilidades para los valores en esos bordes, permite que el resto del proceso se analice de manera sistemática debido a su aciclicidad. En esta aplicación, la idea de romper los bordes de esta manera se llama "desgarro". ^[17]

En el dibujo de grafos en capas , los vértices de un grafo dirigido dado se dividen en una secuencia ordenada de subconjuntos (las capas del dibujo), y cada subconjunto se coloca a lo largo de una línea horizontal de este dibujo, con los bordes extendiéndose hacia arriba y hacia abajo entre estas capas. En este tipo de dibujo, es deseable que la mayoría o todos los bordes estén orientados de manera uniforme hacia abajo, en lugar de mezclar bordes hacia arriba y hacia abajo, para que las relaciones de alcanzabilidad en el dibujo sean más evidentes visualmente. Esto se logra encontrando un conjunto de arcos de retroalimentación mínimos, invirtiendo los bordes en ese conjunto y luego eligiendo la partición en capas de una manera que sea consistente con un orden topológico del grafo acíclico resultante. ^{[18] [19]} Los conjuntos de arcos de retroalimentación también se han utilizado para un subproblema diferente del dibujo de grafos en capas, el ordenamiento de vértices dentro de pares consecutivos de capas. ^[20]

En la resolución de bloqueos en sistemas operativos , el problema de eliminar la menor cantidad de dependencias para romper un bloqueo se puede modelar como el de encontrar un conjunto de arco de retroalimentación mínimo. ^{[21] [22]} Sin embargo, debido a la dificultad computacional de encontrar este conjunto y la necesidad de velocidad dentro de los componentes del sistema operativo, a menudo se utilizan heurísticas en lugar de algoritmos exactos en esta aplicación. ^[22]

Algoritmos

Equivalencias

El conjunto de arcos de retroalimentación mínimos y el subgrafo acíclico máximo son equivalentes a los efectos de la optimización exacta, ya que uno es el conjunto complementario del otro. Sin embargo, para la complejidad parametrizada y la aproximación, difieren, porque el análisis utilizado para esos tipos de algoritmos depende del tamaño de la solución y no solo del tamaño del grafo de entrada, y el conjunto de arcos de retroalimentación mínimos y el subgrafo acíclico máximo tienen tamaños diferentes entre sí. ^[23]

Un conjunto de arcos de retroalimentación de un grafo dado es lo mismo que un conjunto de vértices de retroalimentación de un grafo de línea dirigido de . Aquí, un conjunto de vértices de retroalimentación se define de manera análoga a un conjunto de arcos de retroalimentación, como un subconjunto de los vértices del grafo cuya eliminación eliminaría todos los ciclos. El grafo de línea de un grafo dirigido tiene un vértice para cada arista de , y una arista para cada camino de dos aristas en . En la otra dirección, el conjunto de vértices de retroalimentación mínimo de un grafo dado se puede obtener a partir de la solución a un problema de conjunto de arcos de retroalimentación mínimo en un grafo obtenido al dividir cada vértice de en dos vértices, uno para las aristas entrantes y otro para las aristas salientes. Estas transformaciones permiten que los algoritmos exactos para los conjuntos de arcos de retroalimentación y para los conjuntos de vértices de retroalimentación se conviertan entre sí, con una traducción apropiada de sus límites de complejidad. Sin embargo, esta transformación no preserva la calidad de aproximación para el problema del subgrafo acíclico máximo. ^{[21] [24]} ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Un gráfico dirigido con tres componentes fuertemente conectados , el más a la derecha de los cuales se puede dividir en el vértice de articulación en dos componentes biconectados , cada uno de ellos un ciclo de dos vértices. El problema del conjunto de arcos de retroalimentación se puede resolver por separado en cada componente fuertemente conectado y en cada componente biconectado de un componente fuertemente conectado. ${\displaystyle d}$

En las soluciones exactas y aproximadas del problema del conjunto de arcos de retroalimentación, es suficiente resolver por separado cada componente fuertemente conectado del grafo dado, y descomponer estos componentes fuertemente conectados aún más hasta sus componentes biconectados dividiéndolos en los vértices de articulación. La elección de la solución dentro de cualquiera de estos subproblemas no afecta a los demás, y las aristas que no aparecen en ninguno de estos componentes son inútiles para su inclusión en el conjunto de arcos de retroalimentación. ^[25] Cuando uno de estos componentes puede separarse en dos subgrafos desconectados eliminando dos vértices, se aplica una descomposición más complicada, que permite dividir el problema en subproblemas derivados de los componentes triconectados de sus componentes fuertemente conectados. ^[26]

Exacto

Una forma de encontrar el conjunto de arcos de retroalimentación mínimo es buscar un ordenamiento de los vértices de modo que la menor cantidad posible de aristas se dirijan desde los vértices posteriores a los vértices anteriores en el ordenamiento. ^[27] Buscar todas las permutaciones de un gráfico de -vértices llevaría tiempo , pero un método de programación dinámica basado en el algoritmo Held-Karp puede encontrar la permutación óptima en tiempo , también utilizando una cantidad exponencial de espacio. ^{[28] [29]} Un algoritmo de divide y vencerás que prueba todas las particiones de los vértices en dos subconjuntos iguales y recurre dentro de cada subconjunto puede resolver el problema en tiempo , utilizando el espacio polinomial . ^[29] ${\displaystyle n}$ ${\displaystyle O(n!)}$ ${\displaystyle O(n2^{n})}$ ${\displaystyle O(4^{n}/{\sqrt {n}})}$

En la complejidad parametrizada , el tiempo de los algoritmos no se mide solo en términos del tamaño del gráfico de entrada, sino también en términos de un parámetro separado del gráfico. En particular, para el problema del conjunto de arcos de retroalimentación mínimos, el llamado parámetro natural es el tamaño del conjunto de arcos de retroalimentación mínimos. En gráficos con vértices, con parámetro natural , el problema del conjunto de arcos de retroalimentación se puede resolver en tiempo , transformándolo en un problema de conjunto de vértices de retroalimentación equivalente y aplicando un algoritmo de conjunto de vértices de retroalimentación parametrizado. Debido a que el exponente de en este algoritmo es la constante , independiente de , se dice que este algoritmo es manejable con parámetros fijos. ^[30] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle O(n^{4}4^{k}k^{3}k!)}$ ${\displaystyle n}$ ${\displaystyle 4}$ ${\displaystyle k}$

También se han estudiado otros parámetros además del parámetro natural. Un algoritmo manejable con parámetros fijos que utiliza programación dinámica puede encontrar conjuntos de arcos de retroalimentación mínimos en tiempo , ${\displaystyle O(2^{r}m^{4}\log m)}$ donde es el rango del circuito del grafo no dirigido subyacente. El rango del circuito es un análogo no dirigido del conjunto de arcos de retroalimentación, el número mínimo de aristas que se deben eliminar de un grafo para reducirlo a un árbol de expansión ; es mucho más fácil de calcular que el conjunto de arcos de retroalimentación mínimos. ^[24] Para grafos de ancho de árbol , la programación dinámica en una descomposición de árbol del grafo puede encontrar el conjunto de arcos de retroalimentación mínimos en tiempo polinomial en el tamaño del grafo y exponencial en . Bajo la hipótesis de tiempo exponencial , no es posible una mejor dependencia de . ^[31] ${\displaystyle r}$ ${\displaystyle t}$ ${\displaystyle O(t\log t)}$ ${\displaystyle t}$

En lugar de minimizar el tamaño del conjunto de arcos de retroalimentación, los investigadores también han buscado minimizar el número máximo de aristas eliminadas de cualquier vértice. Esta variación del problema se puede resolver en tiempo lineal . ^[32] Todos los conjuntos de arcos de retroalimentación mínimos se pueden enumerar mediante un algoritmo con un retraso polinomial por conjunto. ^[33]

Aproximado

Problema sin resolver en matemáticas :

¿El problema del arco de retroalimentación tiene un algoritmo de aproximación con una relación de aproximación constante?

(más problemas sin resolver en matemáticas)

El algoritmo de aproximación de tiempo polinomial más conocido para el conjunto de arcos de retroalimentación tiene una relación de aproximación no constante . Esto significa que el tamaño del conjunto de arcos de retroalimentación que encuentra es, como máximo, este factor mayor que el óptimo. ^[21] Determinar si el conjunto de arcos de retroalimentación tiene un algoritmo de aproximación de relación constante, o si es necesaria una relación no constante, sigue siendo un problema abierto. ^[34] ${\displaystyle O(\log n\log \log n)}$

El problema del subgrafo acíclico máximo tiene un algoritmo de aproximación fácil que logra una relación de aproximación de : ${\displaystyle {\tfrac {1}{2}}}$

• Fijar un orden arbitrario de los vértices.
• Dividir los bordes en dos subgrafos acíclicos, uno que consiste en los bordes dirigidos de manera consistente con el ordenamiento y el otro que consiste en los bordes dirigidos de manera opuesta al ordenamiento.
• Devuelve el mayor de los dos subgrafos.

Esto se puede mejorar utilizando un algoritmo voraz para elegir el ordenamiento. Este algoritmo encuentra y elimina un vértice cuyos números de aristas entrantes y salientes estén lo más alejados posible, ordena recursivamente el grafo restante y luego coloca el vértice eliminado en un extremo del orden resultante. Para grafos con aristas y vértices, esto produce un subgrafo acíclico con aristas, en tiempo lineal, dando una razón de aproximación de . ^[35] Otro algoritmo de aproximación en tiempo polinomial, más complicado, se aplica a grafos con grado máximo , y encuentra un subgrafo acíclico con aristas, dando una razón de aproximación de la forma . ^{[36] [37]} Cuando , se puede lograr la razón de aproximación . ^[38] ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m/2+n/6}$ ${\displaystyle {\tfrac {1}{2}}+\Omega (n/m)}$ ${\displaystyle \Delta }$ ${\displaystyle m/2+\Omega (m/{\sqrt {\Delta }})}$ ${\displaystyle {\tfrac {1}{2}}+\Omega (1/{\sqrt {\Delta }})}$ ${\displaystyle \Delta =3}$ ${\displaystyle 8/9}$

Entradas restringidas

En los grafos planos dirigidos , el problema del conjunto de arcos de retroalimentación es dual al problema de contraer un conjunto de aristas (un dijoin ) para hacer que el grafo resultante sea fuertemente conexo . ^[39] Este problema dual es solucionable polinomialmente, ^[40] y por lo tanto el problema del conjunto de arcos de retroalimentación mínimos planos también lo es. ^{[41] [40]} Se puede resolver en el tiempo . ^[42] ${\displaystyle O(n^{5/2}\log n)}$ Una versión ponderada del problema se puede resolver en el tiempo , ^[39] ${\displaystyle O(n^{3})}$ o cuando los pesos son números enteros positivos que son como máximo un número , ${\displaystyle N}$ en el tiempo . ^[42] ${\displaystyle O(n^{5/2}\log nN)}$ Estos algoritmos planos se pueden extender a los grafos que no tienen el grafo de utilidad como un grafo menor , usando el hecho de que los componentes triconectados de estos grafos son planos o de tamaño acotado. ^[26] Los grafos planos también se han generalizado de una manera diferente a una clase de grafos dirigidos llamados dígrafos débilmente acíclicos , definidos por la integralidad de un cierto politopo asociado con sus conjuntos de arcos de retroalimentación . Todo grafo dirigido plano es débilmente acíclico en este sentido, y el problema del conjunto de arcos de retroalimentación se puede resolver en tiempo polinomial para todos los dígrafos débilmente acíclicos. ^[43] ${\displaystyle K_{3,3}}$

Los gráficos de flujo reducibles son otra clase de gráficos dirigidos en los que el problema del arco de retroalimentación puede resolverse en tiempo polinomial. Estos gráficos describen el flujo de control en programas estructurados para muchos lenguajes de programación. Aunque los programas estructurados a menudo producen gráficos de flujo dirigidos planares, la definición de reducibilidad no requiere que el gráfico sea planar. ^[44]

Cuando el problema del conjunto de arcos de retroalimentación mínimos se restringe a torneos , tiene un esquema de aproximación de tiempo polinomial , que se generaliza a una versión ponderada del problema. ^[45] También se conoce un algoritmo parametrizado subexponencial para conjuntos de arcos de retroalimentación ponderados en torneos. ^[14] El problema del subgrafo acíclico máximo para grafos densos también tiene un esquema de aproximación de tiempo polinomial. Sus ideas principales son aplicar redondeo aleatorio a una relajación de programación lineal del problema y desaleatorizar el algoritmo resultante usando paseos en grafos expansores . ^{[34] [46]}

Dureza

Dureza NP

La reducción de completitud NP de Karp y Lawler, desde la cobertura de vértices del grafo amarillo grande hasta el conjunto de arcos de retroalimentación mínimos en el grafo azul pequeño, expande cada vértice amarillo en dos vértices adyacentes del grafo azul, y cada arista amarilla no dirigida en dos aristas dirigidas opuestas. La cobertura de vértices mínima (vértices amarillos superior izquierdo e inferior derecho) corresponde al conjunto de arcos de retroalimentación mínimos rojos.

Para aplicar la teoría de NP-completitud al conjunto de arcos de retroalimentación mínimos, es necesario modificar el problema para que pase de ser un problema de optimización (cuántas aristas se pueden eliminar para romper todos los ciclos) a una versión de decisión equivalente , con una respuesta de sí o no (es posible eliminar aristas). Por lo tanto, la versión de decisión del problema del conjunto de arcos de retroalimentación toma como entrada tanto un grafo dirigido como un número . Pregunta si todos los ciclos se pueden romper eliminando como máximo aristas, o equivalentemente si hay un subgrafo acíclico con al menos aristas. Este problema es NP-completo , lo que implica que ni él ni el problema de optimización se espera que tengan algoritmos de tiempo polinomial. Fue uno de los 21 problemas NP-completos originales de Richard M. Karp ; su NP-completitud fue probada por Karp y Eugene Lawler al mostrar que las entradas para otro problema difícil, el problema de cobertura de vértices , se podían transformar ("reducir") en entradas equivalentes al problema de decisión del conjunto de arcos de retroalimentación. ^{[47] [48]} ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle |E(G)|-k}$

Algunos problemas NP-completos pueden resultar más sencillos cuando sus entradas se limitan a casos especiales. Pero en el caso especial más importante del problema del arco de retroalimentación, el caso de los torneos, el problema sigue siendo NP-completo. ^{[49] [50]}

Inaproximabilidad

La clase de complejidad APX se define como compuesta por problemas de optimización que tienen un algoritmo de aproximación de tiempo polinomial que logra una relación de aproximación constante . Aunque no se conocen tales aproximaciones para el problema del conjunto de arcos de retroalimentación, se sabe que el problema es APX-hard , lo que significa que se podrían usar aproximaciones precisas para él para lograr aproximaciones igualmente precisas para todos los demás problemas en APX. Como consecuencia de su prueba de dureza, a menos que P = NP , no tiene una relación de aproximación de tiempo polinomial mejor que 1.3606. Este es el mismo umbral de dureza de aproximación que se conoce para la cobertura de vértices, y la prueba usa la reducción de Karp-Lawler de la cobertura de vértices al conjunto de arcos de retroalimentación, que preserva la calidad de las aproximaciones. ^{[34] [51] [52] [53]} Mediante una reducción diferente, el problema del subgrafo acíclico máximo también es APX-hard, y NP-hard para aproximarse dentro de un factor de 65/66 del óptimo. ^[38]

La dificultad de aproximación de estos problemas también se ha estudiado bajo supuestos de dificultad computacional no probados que son estándar en la teoría de la complejidad computacional pero más fuertes que P ≠ NP. Si la conjetura de juegos únicos es verdadera, entonces el problema del conjunto de arco de retroalimentación mínimo es difícil de aproximar en tiempo polinomial dentro de cualquier factor constante, y el problema del conjunto de arco de retroalimentación máximo es difícil de aproximar dentro de un factor de , ${\displaystyle {\tfrac {1}{2}}+\varepsilon }$ para cada . ^[54] ${\displaystyle \varepsilon >0}$ Más allá del tiempo polinomial para algoritmos de aproximación, si la hipótesis del tiempo exponencial es verdadera, entonces para cada el conjunto de arco de retroalimentación mínimo no tiene una aproximación dentro de un factor que pueda calcularse en el límite de tiempo subexponencial . ^[55] ${\displaystyle \varepsilon >0}$ ${\displaystyle {\tfrac {7}{6}}-\varepsilon }$ ${\displaystyle O(2^{n^{1-\varepsilon }})}$

Teoría

En los grafos dirigidos planares, el problema del conjunto de arcos de retroalimentación obedece a un teorema mínimo-máximo : el tamaño mínimo de un conjunto de arcos de retroalimentación es igual al número máximo de ciclos dirigidos disjuntos en las aristas que se pueden encontrar en el grafo. ^{[41] [56]} Esto no es cierto para algunos otros grafos; por ejemplo, la primera ilustración muestra una versión dirigida del grafo no planar en el que el tamaño mínimo de un conjunto de arcos de retroalimentación es dos, mientras que el número máximo de ciclos dirigidos disjuntos en las aristas es solo uno. ${\displaystyle K_{3,3}}$

Cada grafo de torneo tiene un camino hamiltoniano , y los caminos hamiltonianos corresponden uno a uno con conjuntos de arcos de retroalimentación mínimos, disjuntos del camino correspondiente. El camino hamiltoniano para un conjunto de arcos de retroalimentación se encuentra invirtiendo sus arcos y encontrando un orden topológico del torneo acíclico resultante. Cada par consecutivo del orden debe ser disjunto de los conjuntos de arcos de retroalimentación, porque de lo contrario uno podría encontrar un conjunto de arcos de retroalimentación más pequeño invirtiendo ese par. Por lo tanto, este ordenamiento da un camino a través de arcos del torneo original, cubriendo todos los vértices. A la inversa, desde cualquier camino hamiltoniano, el conjunto de aristas que conectan vértices posteriores en el camino con los anteriores forma un conjunto de arcos de retroalimentación. Es mínimo, porque cada uno de sus aristas pertenece a un ciclo con las aristas del camino hamiltoniano que es disjunto de todos los demás ciclos de este tipo. ^[57] En un torneo, puede ser el caso de que el conjunto de arcos de retroalimentación mínimo y el subgrafo acíclico máximo estén ambos cerca de la mitad de las aristas. Más precisamente, cada grafo de torneo tiene un conjunto de arcos de retroalimentación de tamaño , y algunos torneos requieren tamaño . ^[58] Para casi todos los torneos, el tamaño es al menos . ^[59] Cada grafo acíclico dirigido puede ser incorporado como un subgrafo de un grafo de torneo más grande, de tal manera que es el único conjunto de arco de retroalimentación mínimo del torneo. El tamaño de este torneo ha sido definido como el "número de reversión" de , y entre los grafos acíclicos dirigidos con el mismo número de vértices es el más grande cuando es en sí mismo un torneo (acíclico). ^{[60] [61]} ${\displaystyle {\tbinom {n}{2}}/2-\Omega (n^{3/2})}$ ${\displaystyle {\tbinom {n}{2}}/2-O(n^{3/2})}$ ${\displaystyle {\tbinom {n}{2}}/2-1.73n^{3/2}}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$

Un grafo dirigido tiene un recorrido de Euler siempre que esté fuertemente conectado y cada vértice tenga el mismo número de aristas entrantes y salientes. Para un grafo de este tipo, con aristas y vértices, el tamaño de un conjunto de arcos de retroalimentación mínimos es siempre al menos . Hay infinitos grafos dirigidos eulerianos para los que este límite es estricto. ^[62] Si un grafo dirigido tiene vértices, con como máximo tres aristas por vértice, entonces tiene un conjunto de arcos de retroalimentación de como máximo aristas, y algunos grafos requieren esta cantidad. Si un grafo dirigido tiene aristas, con como máximo cuatro aristas por vértice, entonces tiene un conjunto de arcos de retroalimentación de como máximo aristas, y algunos grafos requieren esta cantidad. ^[63] ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle (m^{2}+mn)/2n^{2}}$ ${\displaystyle n}$ ${\displaystyle n/3}$ ${\displaystyle m}$ ${\displaystyle m/3}$

Referencias

1. "Cuadro principal – Hombres", Río 2016 , Federación Internacional de Voleibol , archivado desde el original el 23 de diciembre de 2016 , consultado el 14 de noviembre de 2021
2. Hubert, Lawrence (1976), "Seriación utilizando medidas de proximidad asimétricas", British Journal of Mathematical and Statistical Psychology , 29 (1): 32–52, doi :10.1111/j.2044-8317.1976.tb00701.x, MR  0429180
3. Remage, Russell Jr.; Thompson, WA Jr. (1966), "Clasificaciones de comparación por pares de máxima verosimilitud", Biometrika , 53 (1–2): 143–149, doi :10.1093/biomet/53.1-2.143, JSTOR  2334060, MR  0196854, PMID  5964054
4. Goddard, Stephen T. (1983), "Ranking en torneos y toma de decisiones grupales", Management Science , 29 (12): 1384–1392, doi :10.1287/mnsc.29.12.1384, MR  0809110; tenga en cuenta que el algoritmo sugerido por Goddard para encontrar clasificaciones de mínima violación es incorrecto
5. Vaziri, Baback; Dabadghao, Shaunak; Yih, Yuehwern; Morin, Thomas L. (enero de 2018), "Propiedades de los métodos de clasificación deportiva" (PDF) , Journal of the Operational Research Society , 69 (5): 776–787, doi :10.1057/s41274-017-0266-8, S2CID  51887586
6. Coppersmith, Don ; Fleischer, Lisa K.; Rurda, Atri (2010), "Ordenar por número ponderado de victorias proporciona una buena clasificación para torneos ponderados", ACM Transactions on Algorithms , 6 (3): A55:1–A55:13, doi :10.1145/1798596.1798608, MR  2682624, S2CID  18416
7. Seyfarth, Robert M. (noviembre de 1976), "Relaciones sociales entre hembras adultas de babuinos", Animal Behaviour , 24 (4): 917–938, doi :10.1016/s0003-3472(76)80022-x, S2CID  54284406
8. Estep, DQ; Crowell-Davis, SL; Earl-Costello, S.-A.; Beatey, SA (enero de 1993), "Cambios en el comportamiento social de las yeguas de caballos de tiro (Equus caballus) coincidentes con el parto", Applied Animal Behaviour Science , 35 (3): 199–213, doi :10.1016/0168-1591(93)90137-e
9. Eickwort, George C. (abril de 2019), "Dominancia en una cucaracha (Nauphoeta)", Insect Behavior , CRC Press, págs. 120-126, doi :10.1201/9780429049262-18, ISBN 978-0-429-04926-2, Identificador único  203898549
10. Slater, Patrick (1961), "Inconsistencias en un programa de comparaciones por pares", Biometrika , 48 (3–4): 303–312, doi :10.1093/biomet/48.3-4.303, JSTOR  2332752
11. Brunk, HD (1960), "Modelos matemáticos para la clasificación a partir de comparaciones por pares", Journal of the American Statistical Association , 55 (291): 503–520, doi :10.2307/2281911, JSTOR  2281911, MR  0115242; publicado en forma preliminar como Documento ASTIA No. AD 206 573, Fuerza Aérea de los Estados Unidos, Oficina de Investigación Científica, noviembre de 1958, hdl : 2027/mdp.39015095254010
12. Thompson, WA Jr.; Remage, Russell Jr. (1964), "Clasificaciones a partir de comparaciones por pares", Annals of Mathematical Statistics , 35 (2): 739–747, doi : 10.1214/aoms/1177703572 , JSTOR  2238526, MR  0161419
13. Kemeny, John G. (otoño de 1959), "Matemáticas sin números", Daedalus , 88 (4): 577–591, JSTOR  20026529
14. Karpinski, Marek ; Schudy, Warren (2010), "Algoritmos más rápidos para torneos de arcos de retroalimentación, agregación de rangos Kemeny y torneos de intermediación", en Cheong, Otfried ; Chwa, Kyung-Yong; Park, Kunsoo (eds.), Algoritmos y computación - 21.º simposio internacional, ISAAC 2010, Isla de Jeju, Corea, 15-17 de diciembre de 2010, Actas, Parte I , Lecture Notes in Computer Science, vol. 6506, Springer, págs. 3–14, arXiv : 1006.4396 , doi :10.1007/978-3-642-17517-6_3, ISBN 978-3-642-17516-9, Número de identificación del sujeto  16512997
15. Unger, Stephen H. (26 de abril de 1957), Un estudio de redes de retroalimentación lógica asincrónica , Informes técnicos, vol. 320, Instituto Tecnológico de Massachusetts, Laboratorio de Investigación en Electrónica, hdl :1721.1/4763
16. Feehrer, John R.; Jordan, Harry F. (diciembre de 1995), "Colocación de puertas de reloj en circuitos optoelectrónicos de tiempo de vuelo", Applied Optics , 34 (35): 8125–8136, Bibcode :1995ApOpt..34.8125F, doi :10.1364/ao.34.008125, PMID  21068927
17. Rosen, Edward M.; Henley, Ernest J. (verano de 1968), "La nueva estequiometría", Chemical Engineering Education , 2 (3): 120–125, archivado desde el original el 2 de agosto de 2021 , consultado el 2 de agosto de 2021
18. Di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1998), "Dibujos en capas de dígrafos", Dibujo de gráficos: algoritmos para la visualización de gráficos , Prentice Hall , págs. 265–302, ISBN 978-0-13-301615-4
19. Bastert, Oliver; Matuszewski, Christian (2001), "Dibujos en capas de dígrafos", en Kaufmann, Michael; Wagner, Dorothea (eds.), Dibujo de gráficos: métodos y modelos , Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, págs. 87–120, doi :10.1007/3-540-44969-8_5, ISBN 978-3-540-42062-0
20. Demetrescu, Camil; Finocchi, Irene (2001), "Romper los ciclos "correctos" y obtener el "mejor" dibujo", ACM Journal of Experimental Algorithmics , 6 : 171–182, MR  2027115
21. Even, G.; Naor, J .; Schieber, B .; Sudan, M. (1998), "Aproximación de conjuntos de retroalimentación mínima y multicortes en gráficos dirigidos", Algorithmica , 20 (2): 151–174, doi :10.1007/PL00009191, MR  1484534, S2CID  2437790
22. Minoura, Toshimi (1982), "Revisión de la prevención de bloqueos", Journal of the ACM , 29 (4): 1023–1048, doi : 10.1145/322344.322351 , MR  0674256, S2CID  5284738
23. Mishra, Sounaka; Sikdar, Kripasindhu (2004), "Sobre la aproximabilidad de ordenamiento lineal y problemas de optimización NP relacionados en gráficos", Discrete Applied Mathematics , 136 (2–3): 249–269, doi :10.1016/S0166-218X(03)00444-X, MR  2045215
24. Hecht, Michael (2017), "Localizaciones exactas de conjuntos de retroalimentación", Theory of Computing Systems , 62 (5): 1048–1084, arXiv : 1702.07612 , doi :10.1007/s00224-017-9777-6, S2CID  18394348
25. Park, S.; Akers, SB (1992), "Un método eficiente para encontrar un conjunto de arcos de retroalimentación mínimos en gráficos dirigidos", Actas del Simposio Internacional IEEE de 1992 sobre Circuitos y Sistemas (ISCAS '92) , vol. 4, págs. 1863–1866, doi :10.1109/iscas.1992.230449, ISBN 0-7803-0593-0, Identificador único  122603659
26. Nutov, Zeev; Penn, Michal (2000), "Sobre la integralidad, estabilidad y composición de empaquetamientos y cubiertas de diciclos", Journal of Combinatorial Optimization , 4 (2): 235–251, doi :10.1023/A:1009802905533, MR  1772828, S2CID  207632524
27. Younger, D. (1963), "Conjuntos de arcos de retroalimentación mínimos para un gráfico dirigido", IEEE Transactions on Circuit Theory , 10 (2): 238–245, doi :10.1109/tct.1963.1082116
28. Lawler, E. (1964), "Un comentario sobre los conjuntos de arcos de retroalimentación mínimos", IEEE Transactions on Circuit Theory , 11 (2): 296–297, doi :10.1109/tct.1964.1082291
29. Bodlaender, Hans L. ; Fomin, Fedor V.; Koster, Arie MCA; Kratsch, Dieter; Thilikos, Dimitrios M. (2012), "Una nota sobre algoritmos exactos para problemas de ordenamiento de vértices en grafos", Theory of Computing Systems , 50 (3): 420–432, doi :10.1007/s00224-011-9312-0, hdl : 1956/4556 , MR  2885638, S2CID  9967521
30. Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "Un algoritmo de parámetros fijos para el problema del conjunto de vértices con retroalimentación dirigida", Journal of the ACM , 55 (5): 1–19, doi :10.1145/1411509.1411511, S2CID  1547510
31. Bonamy, Marthe; Kowalik, Lukasz; Nederlof, Jesper; Pilipczuk, Michal; Socala, Arkadiusz; Wrochna, Marcin (2018), "Sobre el conjunto de vértices de retroalimentación dirigida parametrizado por el ancho del árbol", en Brandstädt, Andreas; Köhler, Ekkehard; Meer, Klaus (eds.), Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Alemania, 27-29 de junio de 2018, Actas , Lecture Notes in Computer Science, vol. 11159, Springer, págs. 65–78, arXiv : 1707.01470 , doi :10.1007/978-3-030-00256-5_6, ISBN 978-3-030-00255-8, S2CID8008855 ​
32. Lin, Lishin; Sahni, Sartaj (1989), "Problemas de eliminación de bordes correctos", IEEE Transactions on Computers , 38 (5): 756–761, doi :10.1109/12.24280, MR  0994519
33. Schwikowski, Benno; Speckenmeyer, Ewald (2002), "Sobre la enumeración de todas las soluciones mínimas de los problemas de retroalimentación", Discrete Applied Mathematics , 117 (1–3): 253–265, doi : 10.1016/S0166-218X(00)00339-5 , MR  1881280
34. Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Minimum Feedback Arc Set", Un compendio de problemas de optimización NP , archivado desde el original el 2021-07-29 , consultado el 2021-07-29
35. Eades, Peter ; Lin, Xuemin; Smyth, WF (1993), "Una heurística rápida y efectiva para el problema del conjunto de arcos de retroalimentación", Information Processing Letters , 47 (6): 319–323, doi :10.1016/0020-0190(93)90079-O, MR  1256786, archivado desde el original el 2020-10-22 , consultado el 2021-08-01
36. Berger, Bonnie ; Shor, Peter W. (1997), "Límites estrictos para el problema del subgrafo acíclico máximo", Journal of Algorithms , 25 (1): 1–18, doi :10.1006/jagm.1997.0864, ​​MR  1474592
37. Hassin, Refael; Rubinstein, Shlomi (1994), "Aproximaciones para el problema del subgrafo acíclico máximo", Information Processing Letters , 51 (3): 133–140, doi :10.1016/0020-0190(94)00086-7, MR  1290207
38. Newman, Alantha (junio de 2000), Aproximación del subgrafo acíclico máximo (tesis de maestría), Massachusetts Institute of Technology, hdl :1721.1/86548, citado por Guruswami et al. (2011)
39. Gabow, Harold N. (1995), "Centroides, representaciones y flujos submodulares", Journal of Algorithms , 18 (3): 586–628, doi :10.1006/jagm.1995.1022, MR  1334365
40. Frank, András (1981), "Cómo hacer un dígrafo fuertemente conectado", Combinatorica , 1 (2): 145–153, doi :10.1007/BF02579270, MR  0625547, S2CID  27825518
41. Lucchesi, CL; Younger, DH (1978), "Un teorema minimax para grafos dirigidos", Journal of the London Mathematical Society , Segunda serie, 17 (3): 369–374, doi :10.1112/jlms/s2-17.3.369, MR  0500618
42. Gabow, Harold N. (1993), "Un marco para algoritmos de escalamiento de costos para problemas de flujo submodular", 34.º Simposio anual sobre fundamentos de la informática, Palo Alto, California, EE. UU., 3-5 de noviembre de 1993 , IEEE Computer Society, págs. 449–458, doi :10.1109/SFCS.1993.366842, ISBN 0-8186-4370-6, MR  1328441, S2CID  32162097
43. Grötschel, Martin ; Jünger, Michael; Reinelt, Gerhard (1985), "Sobre el politopo del subgrafo acíclico", Programación matemática , 33 (1): 28–42, doi :10.1007/BF01582009, MR  0809747, S2CID  206798683
44. Ramachandran, Vijaya (1988), "Encontrar un conjunto de arcos de retroalimentación mínimos en gráficos de flujo reducibles", Journal of Algorithms , 9 (3): 299–313, doi :10.1016/0196-6774(88)90022-3, MR  0955140
45. Kenyon-Mathieu, Claire ; Schudy, Warren (2007), "Cómo clasificar con pocos errores: un PTAS para un arco de retroalimentación ponderada establecido en torneos", en Johnson, David S. ; Feige, Uriel (eds.), Actas del 39.° Simposio Anual de la ACM sobre Teoría de la Computación, San Diego, California, EE. UU., 11-13 de junio de 2007 , págs. 95-103, doi :10.1145/1250790.1250806, S2CID  9436948, ECCC  TR06-144; véase también la versión ampliada del autor Archivado el 15 de enero de 2009 en Wayback Machine.
46. Arora, Sanjeev ; Frieze, Alan ; Kaplan, Haim (2002), "Un nuevo procedimiento de redondeo para el problema de asignación con aplicaciones a problemas de ordenamiento de grafos densos", Mathematical Programming , 92 (1): 1–36, doi :10.1007/s101070100271, MR  1892295, S2CID  3207086, archivado desde el original el 2021-08-03 , consultado el 2021-08-03
47. Karp, Richard M. (1972), "Reducibilidad entre problemas combinatorios", Complejidad de los cálculos informáticos , Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, Nueva York: Plenum, págs. 85-103
48. Garey, Michael R .; Johnson, David S. (1979), "A1.1: GT8", Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, pág. 192, ISBN 0-7167-1045-5
49. Alon, Noga (2006), "Torneos de clasificación", Revista SIAM de Matemáticas Discretas , 20 (1): 137–142, doi :10.1137/050623905, MR  2257251
50. Charbit, Pierre; Thomassé, Stéphan; Yeo, Anders (2007), "El problema del arco de retroalimentación mínima es NP-difícil para torneos" (PDF) , Combinatorics, Probability and Computing , 16 (1): 1–4, doi :10.1017/S0963548306007887 (inactivo 2024-09-25), MR  2282830, S2CID  36539840{{citation}}: CS1 maint: DOI inactivo a partir de septiembre de 2024 ( enlace )
51. Ausiello, G .; D'Atri, A.; Protasi, M. (1980), "Reducciones que preservan la estructura entre problemas de optimización convexa", Journal of Computer and System Sciences , 21 (1): 136–153, doi :10.1016/0022-0000(80)90046-X, MR  0589808
52. Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF) (tesis doctoral), Departamento de Análisis Numérico y Ciencias de la Computación, Instituto Real de Tecnología, Estocolmo, archivado (PDF) desde el original el 29 de diciembre de 2010 , consultado el 11 de octubre de 2007
53. Dinur, Irit ; Safra, Samuel (2005), "Sobre la dificultad de aproximar la cobertura mínima de vértices" (PDF) , Annals of Mathematics , 162 (1): 439–485, doi : 10.4007/annals.2005.162.439 , archivado (PDF) desde el original el 20 de septiembre de 2009 , consultado el 29 de julio de 2021; versión preliminar en Dinur, Irit ; Safra, Samuel (2002), "La importancia de estar sesgado", en Reif, John H. (ed.), Actas del 34º Simposio Anual de la ACM sobre Teoría de la Computación, 19-21 de mayo de 2002, Montreal, Québec, Canadá , págs. 33–42, doi :10.1145/509907.509915, ISBN 1-58113-495-9, Número de identificación del sujeto  1235048
54. Guruswami, Venkatesan ; Håstad, Johan ; Manokaran, Rajsekar; Raghavendra, Prasad; Charikar, Moses (2011), "Superar el ordenamiento aleatorio es difícil: cada CSP de ordenamiento es resistente a la aproximación" (PDF) , SIAM Journal on Computing , 40 (3): 878–914, doi :10.1137/090756144, MR  2823511, archivado (PDF) del original el 2021-07-31 , recuperado 2021-07-31
55. Bonnet, Édouard; Paschos, Vangelis Th. (2018), "Esparsificación y aproximación subexponencial", Acta Informatica , 55 (1): 1–15, arXiv : 1402.2843 , doi :10.1007/s00236-016-0281-2, MR  3757549, S2CID  3136275
56. Lovász, László (1976), "Sobre dos teoremas minimax en grafos", Journal of Combinatorial Theory , Serie B, 21 (2): 96–103, doi : 10.1016/0095-8956(76)90049-6 , MR  0427138
57. Bar-Noy, Amotz; Naor, Joseph (1990), "Ordenamiento, conjuntos de retroalimentación mínima y caminos de Hamilton en torneos", SIAM Journal on Discrete Mathematics , 3 (1): 7–20, doi :10.1137/0403002, MR  1033709
58. Spencer, J. (1980), "Ranking óptimo de torneos no clasificables", Periodica Mathematica Hungarica , 11 (2): 131–144, doi :10.1007/BF02017965, MR  0573525, S2CID  119894999
59. Fernandez de la Vega, W. (1983), "Sobre la cardinalidad máxima de un conjunto consistente de arcos en un torneo aleatorio", Journal of Combinatorial Theory , Serie B, 35 (3): 328–332, doi : 10.1016/0095-8956(83)90060-6 , MR  0735201
60. Barthélémy, Jean-Pierre; Hudry, Olivier; Isaak, Garth; Roberts, Fred S .; Tesman, Barry (1995), "El número inverso de un dígrafo", Discrete Applied Mathematics , 60 (1–3): 39–76, doi :10.1016/0166-218X(94)00042-C, MR  1339075
61. Isaak, Garth; Narayan, Darren A. (2004), "Una clasificación de torneos que tienen un torneo acíclico como un conjunto de arco de retroalimentación mínimo", Information Processing Letters , 92 (3): 107–111, doi :10.1016/j.ipl.2004.07.001, MR  2095357
62. Huang, Hao; Ma, Jie; Shapira, Asaf; Sudakov, Benny ; Yuster, Raphael (2013), "Grandes conjuntos de arcos de retroalimentación, subgrafos de alto grado mínimo y ciclos largos en dígrafos eulerianos", Combinatorics, Probability and Computing , 22 (6): 859–873, arXiv : 1202.2602 , doi : 10.1017/S0963548313000394, hdl : 20.500.11850/73894 , MR  3111546, S2CID  7967738
63. Hanauer, Kathrin; Brandenburg, Franz-Josef; Auer, Christopher (2013), "Límites superiores ajustados para conjuntos de arcos de retroalimentación mínimos de grafos regulares", en Brandstädt, Andreas; Jansen, Klaus; Reischuk, Rüdiger (eds.), Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Alemania, 19-21 de junio de 2013, Documentos revisados , Lecture Notes in Computer Science, vol. 8165, Springer, págs. 298-309, doi :10.1007/978-3-642-45043-3_26, ISBN 978-3-642-45042-6, Sr.  3139198