ancho de corte

Propiedad en teoría de grafos

Un gráfico de ancho de corte 2. Para el orden de vértices de izquierda a derecha que se muestra, cada línea vertical cruza como máximo dos bordes.

En teoría de grafos , el ancho de corte de un gráfico no dirigido es el entero más pequeño con la siguiente propiedad: existe un ordenamiento de los vértices del gráfico, tal que cada corte obtenido al dividir los vértices en subconjuntos anteriores y posteriores del ordenamiento es atravesado por en la mayoría de los bordes. Es decir, si los vértices están numerados , entonces para cada , el número de aristas con y es como máximo . ^[1] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle v_{1},v_{2},\dots v_{n}}$ ${\displaystyle \ell =1,2,\dots n-1}$ ${\displaystyle v_{i}v_{j}}$ ${\displaystyle i\leq \ell }$ ${\displaystyle j>\ell }$ ${\displaystyle k}$

Al ancho de corte de un gráfico también se le ha llamado número de plegado . ^[1] Tanto el orden de los vértices que produce el ancho de corte como el problema de calcular este orden y el ancho de corte se han denominado disposición lineal de corte mínimo . ^[2]

Relación con otros parámetros

El ancho de corte está relacionado con varios otros parámetros de ancho de los gráficos. En particular, siempre es al menos tan grande como el ancho del árbol o el ancho de ruta del mismo gráfico. Sin embargo, es como máximo el ancho de la ruta multiplicado por , o el ancho del árbol multiplicado por donde es el grado máximo y es el número de vértices. ^{[3] [4]} Si una familia de gráficos tiene un grado máximo acotado y sus gráficos no contienen subdivisiones de árboles binarios completos de tamaño ilimitado, entonces los gráficos de la familia tienen un ancho de corte acotado. ^[4] En gráficos subcúbicos (gráficos de grado tres como máximo), el ancho de corte es igual al ancho de ruta más uno. ^[5] ${\displaystyle O(\Delta )}$ ${\displaystyle O(\Delta \log n)}$ ${\displaystyle \Delta }$ ${\displaystyle n}$

El ancho de corte es mayor o igual al número mínimo de bisección de cualquier gráfico. Este es el número mínimo posible de aristas de un lado a otro para una partición de los vértices en dos subconjuntos de igual tamaño (o lo más parecido posible). Cualquier diseño lineal de un gráfico, que logra su ancho de corte óptimo, también proporciona una bisección con el mismo número de aristas, obtenida dividiendo el diseño en su primera y segunda mitad. El ancho de corte es menor o igual al grado máximo multiplicado por el ancho de banda del gráfico , el número máximo de pasos que separan los puntos finales de cualquier borde en una disposición lineal elegida para minimizar esta cantidad. ^[6] A diferencia del ancho de banda, el ancho de corte no cambia cuando los bordes se subdividen en rutas de más de un borde. Está estrechamente relacionado con el "ancho de banda topológico", el ancho de banda mínimo que se puede obtener subdividiendo los bordes de un gráfico determinado. En particular, para cualquier árbol se encuentra entre el ancho de banda topológico y un número ligeramente mayor, . ^[1] ${\displaystyle b^{*}}$ ${\displaystyle b^{*}+\log _{2}b^{*}+2}$

Otro parámetro, definido de manera similar al ancho de corte en términos de número de bordes que abarcan cortes en un gráfico, es el ancho de tallado . Sin embargo, en lugar de utilizar un orden lineal de vértices y una secuencia lineal de cortes, como en el ancho de corte, el ancho de tallado utiliza cortes derivados de una agrupación jerárquica de vértices, lo que lo relaciona más estrechamente con el ancho de árbol o el ancho de rama y es menos similar a los otros parámetros de ancho. que involucran ordenamientos lineales como ancho de ruta o ancho de banda. ^[7]

El ancho de corte se puede utilizar para proporcionar un límite inferior en otro parámetro, el número de cruce , que surge en el estudio de dibujos de gráficos . El número de cruce de un gráfico es el número mínimo de pares de aristas que se cruzan, en cualquier dibujo del gráfico en el plano donde cada vértice toca solo las aristas de las que es punto final. En gráficas de grado acotado, el número de cruce es siempre al menos proporcional al cuadrado del ancho de corte. Un límite más preciso, que se aplica a gráficos donde los grados no están limitados, es: ^[8]

$${\displaystyle \operatorname {crossings} (G)\geq {\frac {1}{1176}}\operatorname {cutwidth} (G)^{2}-\sum _{v\in V(G)}\left({\frac {\deg(v)}{4}}\right)^{2}.}$$

gráficas planas^[8]la incrustación de librospáginas de semiplanoancho de página^[9]

Complejidad computacional

Se puede encontrar el ancho de corte y construir un diseño lineal de ancho óptimo, a tiempo para un árbol de vértices. ^[10] Para gráficos más generales, es NP-duro . Sigue siendo NP-duro incluso para gráficos planos de grado máximo tres, y una versión ponderada del problema (minimizando el peso de los bordes en cualquier corte de una disposición lineal) es NP-duro incluso cuando la entrada es un árbol. ^[11] ${\displaystyle O(n\log n)}$ ${\displaystyle n}$

El ancho de corte es uno de los muchos problemas de disposición lineal óptima que se pueden resolver exactamente en el tiempo mediante el algoritmo de Held-Karp , utilizando programación dinámica . ^[12] También se conoce un algoritmo cuántico más rápido con el tiempo . ^[13] Además, es manejable con parámetros fijos : para cualquier valor fijo de , es posible probar si un gráfico tiene un ancho de corte como máximo y, de ser así, encontrar un orden de vértices óptimo para él, en tiempo lineal . ^[2] Más precisamente, en términos de y , el tiempo de ejecución de este algoritmo es . ^[14] Un algoritmo parametrizado alternativo, más adecuado para gráficos en los que un pequeño número de vértices tienen un alto grado (haciendo que el ancho de corte sea grande), resuelve el problema en tiempo polinómico cuando el gráfico tiene una cobertura de vértices de tamaño acotado, transformándolo en un problema de programación entera con pocas variables y límites polinomiales en los valores de las variables. Queda abierto si el problema se puede resolver de manera eficiente para gráficos de ancho de árbol acotado, que incluirían ambas parametrizaciones por ancho de corte y número de cobertura de vértice. ^[15] ${\displaystyle O(n2^{n})}$ ${\displaystyle O(1.817^{n})}$ ${\displaystyle c}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle c}$ ${\textstyle 2^{O(c^{2})}n}$ ${\displaystyle n}$

Cutwidth tiene un esquema de aproximación de tiempo polinomial para gráficos densos , ^[16] pero para gráficos que pueden no ser densos, la mejor relación de aproximación conocida es . ^[17] Esto proviene de un método de Tom Leighton y Satish Rao para reducir el ancho de corte aproximado al número mínimo de bisección, perdiendo un factor de en la relación de aproximación, mediante el uso de bisección recursiva para ordenar los vértices. ^[18] Combinando este método de bisección recursiva con otro método de Sanjeev Arora , Rao y Umesh Vazirani para aproximar el número mínimo de bisección, ^[19] se obtiene la relación de aproximación indicada. ^[17] Según la hipótesis de expansión de conjuntos pequeños , no es posible lograr una relación de aproximación constante. ^[17] ${\textstyle O{\bigl (}(\log n)^{3/2}{\bigr )}}$ ${\displaystyle \log _{2}n}$

Aplicaciones

Una de las primeras aplicaciones motivadoras para el ancho de corte involucró el enrutamiento de canales en el diseño VLSI , en el que los componentes dispuestos a lo largo de la parte superior e inferior de una región rectangular de un circuito integrado deben conectarse mediante conductores que conectan pares de pines unidos a los componentes. Si los componentes pueden organizarse en diferentes órdenes de izquierda a derecha, pero los pines de cada componente deben permanecer contiguos, entonces esto puede traducirse en un problema de elegir una disposición lineal de un gráfico con un vértice para cada componente y un borde para cada conexión pin a pin. El ancho de corte del gráfico controla la cantidad de canales necesarios para enrutar el circuito. ^[5]

En ingeniería de proteínas , se ha utilizado la suposición de que un gráfico asociado tiene un ancho de corte limitado para acelerar la búsqueda de secuencias de ARNm que codifican simultáneamente una secuencia de proteína determinada y se pliegan en una estructura secundaria determinada . ^[20]

Se ha aplicado una variante ponderada del problema que se aplica a gráficos acíclicos dirigidos y que solo permite ordenamientos lineales consistentes con la orientación de los bordes del gráfico para programar una secuencia de tareas computacionales de una manera que minimice la cantidad máxima de memoria requerida en el programa. , tanto para las tareas en sí como para mantener los datos utilizados para la comunicación entre tareas. ^[21] En teoría de bases de datos , la dureza NP del problema del ancho de corte se ha utilizado para mostrar que también es NP-difícil programar la transferencia de bloques de datos entre un disco y la memoria principal cuando se realiza una unión , para evitar transferencias repetidas del mismo bloque mientras se ajusta el cálculo dentro de una cantidad limitada de memoria principal. ^[22]

En el dibujo de gráficos , además de aplicarse en el límite inferior del número de cruce, ^{[8] el ancho de corte se ha aplicado en el estudio de un tipo específico de dibujo de gráficos tridimensional, en el que los bordes se representan como} cadenas poligonales disjuntas con al menos En la mayoría de los pliegues, los vértices se colocan en una línea y todos los vértices y puntos de pliegue deben tener coordenadas enteras. Para dibujos de este tipo, el volumen mínimo de un cuadro delimitador del dibujo debe ser al menos proporcional al ancho de corte multiplicado por el número de vértices. Siempre existe un dibujo con este volumen, con los vértices colocados sobre una línea paralela al eje. ^[23]

Referencias

1. Chung, Fan RK (1985). "Sobre el ancho de corte y el ancho de banda topológico de un árbol" (PDF) . Revista SIAM de Métodos Algebraicos y Discretos . 6 (2): 268–277. doi :10.1137/0606026. SEÑOR  0778007.
2. Thilikos, Dimitrios M.; Serna, María ; Bodlaender, Hans L. (2005). "Ancho de corte I: un algoritmo de parámetro fijo en tiempo lineal" (PDF) . Revista de algoritmos . 56 (1): 1–24. doi :10.1016/j.jalgor.2004.12.001. SEÑOR  2146375.
3. Koraj, Efraín; Solel, Nir (1993). "Ancho de árbol, ancho de camino y ancho de corte". Matemática Aplicada Discreta . 43 (1): 97-101. doi : 10.1016/0166-218X(93)90171-J . SEÑOR  1218045.
4. Chung, FRK ; Seymour, PD (1989). "Gráficos con ancho de banda y ancho de corte pequeños" (PDF) . Matemáticas discretas . 75 (1–3): 113–119. doi :10.1016/0012-365X(89)90083-6. SEÑOR  1001391.
5. Makedon, Fillia ; Sudborough, Ivan Hal (1989). "Sobre minimizar el ancho en diseños lineales". Matemática Aplicada Discreta . 23 (3): 243–265. doi : 10.1016/0166-218X(89)90016-4 . SEÑOR  0996137.
6. Díaz, Josep; Petit, Jordi; Serna, María (septiembre de 2002). "Un estudio de problemas de diseño de gráficos" (PDF) . Encuestas de Computación ACM . 34 (3): 313–356. doi :10.1145/568522.568523.
7. Seymour, Paul D .; Thomas, Robin (1994). "Enrutamiento de llamadas y cazador de ratas". Combinatoria . 14 (2): 217–241. doi :10.1007/BF01215352.
8. Djidjev, Hristo N.; Vrt'o, Imrich (2003). "Cruce de números y anchos de corte". Revista de aplicaciones y algoritmos de gráficos . 7 (3): 245–251. doi : 10.7155/jgaa.00069 . SEÑOR  2112230.
9. Stöhr, Elena (1988). "Una compensación entre el número de página y el ancho de página de las incrustaciones de gráficos en libros". Información y Computación . 79 (2): 155-162. doi : 10.1016/0890-5401(88)90036-3 . SEÑOR  0968104.
10. Yannakakis, Mihalis (1985). "Un algoritmo polinómico para la disposición lineal de árboles con corte mínimo". Revista de la ACM . 32 (4): 950–988. doi : 10.1145/4221.4228 . SEÑOR  0810346.
11. Monien, B.; Sudborough, Illinois (1988). "El corte mínimo es NP completo para árboles con peso en los bordes". Informática Teórica . 58 (1–3): 209–229. doi : 10.1016/0304-3975(88)90028-X . SEÑOR  0963264.
12. 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 gráficos". Teoría de los Sistemas Computacionales . 50 (3): 420–432. doi :10.1007/s00224-011-9312-0. hdl : 1956/4556 . SEÑOR  2885638. S2CID  9967521.
13. Ambainis, Andris; Balodis, Kaspars; Iraids, Jānis; Kokainis, Martins; Prūsis, Krišjānis; Vihrovs, Jevgēnijs (2019). "Aceleraciones cuánticas para algoritmos de programación dinámica de tiempo exponencial". En Chan, Timothy M. (ed.). Actas del trigésimo simposio anual ACM-SIAM sobre algoritmos discretos, SODA 2019, San Diego, California, EE. UU., 6 al 9 de enero de 2019 . Sociedad de Matemática Industrial y Aplicada. págs. 1783-1793. arXiv : 1807.05209 . doi :10.1137/1.9781611975482.107. SEÑOR  3909576.
14. Giannopoulou, Archontia C.; Pilipczuk, Jean-Florent, Michałand Raymond; Thilikos, Dimitrios M.; Wrochna, Marcin (2019). «Ancho de corte: obstrucciones y aspectos algorítmicos» (PDF) . Algorítmica . 81 (2): 557–588. doi :10.1007/s00453-018-0424-7. SEÑOR  3910081.{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
15. Becarios, Michael R .; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances A .; Saurabh, Saket (2008). "Problemas de diseño de gráficos parametrizados por cobertura de vértices" (PDF) . En Hong, Seok-Hee ; Nagamochi, Hiroshi; Fukunaga, Takuro (eds.). Algoritmos y Computación, XIX Simposio Internacional, ISAAC 2008, Gold Coast, Australia, 15 al 17 de diciembre de 2008, Actas . Apuntes de conferencias sobre informática. vol. 5369. Saltador. págs. 294–305. doi :10.1007/978-3-540-92182-0_28.
16. Arora, Sanjeev ; Friso, Alan ; Kaplan, Haim (2002). "Un nuevo procedimiento de redondeo para el problema de asignación con aplicaciones a problemas de disposición de gráficos densos". Programación Matemática . 92 (1, Serie A): 1–36. doi :10.1007/s101070100271. SEÑOR  1892295.
17. Wu, Yu; Austrian, Per; Pitassi, Toniann ; Liu, David (2014). "Inaccesibilidad del ancho de los árboles, guijarros de un solo uso y problemas de diseño relacionados". Revista de investigación en inteligencia artificial . 49 : 569–600. doi : 10.1613/jair.4030 . SEÑOR  3195329.
18. Leighton, Tom ; Rao, Satish (1999). "Teoremas de corte mínimo de flujo máximo de múltiples productos y su uso en el diseño de algoritmos de aproximación". Revista de la ACM . 46 (6): 787–832. doi : 10.1145/331524.331526 . SEÑOR  1753034.
19. Arora, Sanjeev ; Rao, Satish ; Vazirani, Umesh (2009). "Flujos expansores, incrustaciones geométricas y partición de gráficos" (PDF) . Revista de la ACM . 56 (2): art. 5, 37. doi :10.1145/1502793.1502794. SEÑOR  2535878.
20. Blin, Guillaume; Fertín, Guillaume; Hermelín, Danny; Vialette, Stéphane (2008). "Algoritmos de parámetros fijos para la búsqueda de similitudes de proteínas bajo restricciones de estructura de ARNm". Revista de algoritmos discretos . 6 (4): 618–626. doi : 10.1016/j.jda.2008.03.004 . SEÑOR  2463425.
21. Kayaaslan, Enver; Lamberto, Thomas; Marchal, Loris; Uçar, Bora (2018). "Programación de gráficos de tareas en serie paralela para minimizar el pico de memoria". Informática Teórica . 707 : 1–23. doi : 10.1016/j.tcs.2017.09.037 . SEÑOR  3734396.
22. Fotouhi, Farshad; Pramanik, Sakti (1991). "El problema de optimizar el número de accesos a bloques al realizar una unión relacional es NP-difícil". Cartas de procesamiento de información . 38 (5): 271–275. doi :10.1016/0020-0190(91)90070-X. SEÑOR  1114421.
23. Morin, Pat ; Madera, David R. (2004). "Dibujos de gráficos tridimensionales de 1 pliegue". Revista de aplicaciones y algoritmos de gráficos . 8 (3): 357–366. doi : 10.7155/jgaa.00095 . SEÑOR  2176967.