Ancho de corte

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

El ancho de corte de un gráfico también se ha denominado 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 grafos. En particular, siempre es al menos tan grande como el ancho del árbol o el ancho del camino del mismo grafo. Sin embargo, es como máximo el ancho del camino 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 grafos tiene un grado máximo acotado, y sus grafos no contienen subdivisiones de árboles binarios completos de tamaño ilimitado, entonces los grafos de la familia tienen un ancho de corte acotado. ^[4] En grafos subcúbicos (grafos de grado máximo tres), el ancho de corte es igual al ancho del camino más uno. ^[5] $O(\Delta )$ $O(\Delta \log n)$ ${\estilo de visualización \Delta}$ ${\estilo de visualización n}$

El ancho de corte es mayor o igual que el número mínimo de bisecciones de cualquier grafo. 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 grafo, que logre su ancho de corte óptimo, también proporciona una bisección con el mismo número de aristas, obtenida al dividir el diseño en sus mitades primera y segunda. El ancho de corte es menor o igual que el grado máximo multiplicado por el ancho de banda del grafo , el número máximo de pasos que separan los puntos finales de cualquier arista en una disposición lineal elegida para minimizar esta cantidad. ^[6] A diferencia del ancho de banda, el ancho de corte no cambia cuando las aristas se subdividen en caminos de más de una arista. Está estrechamente relacionado con el "ancho de banda topológico", el ancho de banda mínimo que se puede obtener al subdividir las aristas de un grafo dado. En particular, para cualquier árbol está intercalado entre el ancho de banda topológico y un número ligeramente mayor, . ^[1] $estilo de visualización b^{*}}$ $Estilo de visualización b^{*}+\log _{2}b^{*}+2}$

Otro parámetro, definido de manera similar a cutwidth en términos de números de aristas que abarcan cortes en un gráfico, es el ancho de tallado . Sin embargo, en lugar de utilizar un ordenamiento lineal de vértices y una secuencia lineal de cortes, como en cutwidth, el ancho de tallado utiliza cortes derivados de una agrupación jerárquica de vértices, lo que lo hace más relacionado con treewidth o branchwidth y menos similar a los otros parámetros de ancho que involucran ordenamientos lineales como pathwidth o widthwide. ^[7]

El ancho de corte se puede utilizar para proporcionar un límite inferior en otro parámetro, el número de cruces , que surge en el estudio de dibujos de grafos . El número de cruces de un grafo es el número mínimo de pares de aristas que se intersecan, en cualquier dibujo del grafo en el plano donde cada vértice toca solo las aristas para las que es un punto final. En grafos de grado acotado, el número de cruces es siempre al menos proporcional al cuadrado del ancho de corte. Un límite más preciso, que se aplica a grafos donde los grados no están acotados, es: ^[8] Aquí, el término de corrección, proporcional a la suma de los grados al cuadrado, es necesario para tener en cuenta la existencia de grafos planares cuyo ancho de corte al cuadrado es proporcional a esta cantidad pero cuyo número de cruces es cero. ^[8] En otro estilo de dibujo de grafos, la incrustación de libros , los vértices se disponen en una línea y las aristas se disponen sin cruces en páginas de semiplano separadas que se encuentran en esta línea. El ancho de página de una incrustación de libro se ha definido como el ancho de corte más grande de cualquiera de las páginas, utilizando el mismo orden de vértices. ^[9] $\operatorname {cruces} (G)\geq {\frac {1}{1176}}\operatorname {ancho de corte} (G)^{2}-\sum _{v\in V(G)}\left({\frac {\deg(v)}{4}}\right)^{2}.$

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-hard . Sigue siendo NP-hard incluso para gráficos planares de grado máximo tres, y una versión ponderada del problema (minimizar el peso de los bordes a lo largo de cualquier corte de un arreglo lineal) es NP-hard incluso cuando la entrada es un árbol. ^[11] $O(n\log n)$ ${\estilo de visualización n}$

El ancho de corte es uno de los muchos problemas de ordenamiento lineal óptimo que se pueden resolver exactamente en el tiempo mediante el algoritmo 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 grafo tiene ancho de corte como máximo , y si es así encontrar un ordenamiento de vértices óptimo para él, en tiempo lineal . ^[2] Más precisamente, en términos de ambos y , el tiempo de ejecución de este algoritmo es . ^[14] Un algoritmo parametrizado alternativo, más adecuado para grafos en los que un pequeño número de vértices tienen alto grado (haciendo que el ancho de corte sea grande) resuelve el problema en tiempo polinomial en cuando el grafo tiene una cubierta 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 con un ancho de árbol acotado, lo que incluiría ambas parametrizaciones por ancho de corte y número de cobertura de vértice. ^[15] $O(n2^{n})$ $Estilo de visualización O(1,817^{n})}$ ${\estilo de visualización c}$ ${\estilo de visualización c}$ ${\estilo de visualización n}$ ${\estilo de visualización c}$ ${\textstyle 2^{O(c^{2})}n}$ ${\estilo de visualización n}$

Cutwidth tiene un esquema de aproximación de tiempo polinomial para gráficos densos , ^[16] pero para gráficos que podrían no ser densos la mejor razó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 razó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] da la razón de aproximación establecida. ^[17] Bajo la hipótesis de expansión de conjuntos pequeños , no es posible lograr una razón de aproximación constante. ^[17] ${\textstyle O{\bigl (}(\log n)^{3/2}{\bigr )}}$ $Estilo de visualización: log _{2}n$

Aplicaciones

Una de las primeras aplicaciones motivadoras del ancho de corte fue 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 estar conectados por conductores que conectan pares de pines unidos a los componentes. Si los componentes pueden organizarse libremente en diferentes órdenes de izquierda a derecha, pero los pines de cada componente deben permanecer contiguos, esto se puede traducir en un problema de elección de 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 dada y se pliegan en una estructura secundaria dada . ^[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 minimiza la cantidad máxima de memoria requerida en la programación, tanto para las tareas mismas como para mantener los datos utilizados para la comunicación de tarea a tarea. ^[21] En la teoría de bases de datos , la NP-dureza del problema de corte de ancho se ha utilizado para demostrar que también es NP-duro 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 grafos , además de aplicarse en la cota inferior para el número de cruces, ^[8] el ancho de corte se ha aplicado en el estudio de un tipo específico de dibujo de grafos tridimensionales, en el que las aristas se representan como cadenas poligonales disjuntas con como máximo una curva, los vértices se colocan sobre una línea y todos los vértices y puntos de curvatura 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

^ abc Chung, Fan RK (1985). "Sobre el ancho de corte y el ancho de banda topológico de un árbol" (PDF) . Revista SIAM sobre métodos algebraicos y discretos . 6 (2): 268–277. doi :10.1137/0606026. MR 0778007.
^ ab Thilikos, Dimitrios M.; Serna, María ; Bodlaender, Hans L. (2005). "Ancho de corte I: un algoritmo de parámetro fijo de tiempo lineal" (PDF) . Revista de algoritmos . 56 (1): 1–24. doi :10.1016/j.jalgor.2004.12.001. SEÑOR 2146375.
^ Korach, Ephraim; Solel, Nir (1993). "Ancho de árbol, ancho de ruta y ancho de corte". Matemáticas Aplicadas Discretas . 43 (1): 97–101. doi : 10.1016/0166-218X(93)90171-J . MR 1218045.
^ ab 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. MR 1001391.
^ ab Makedon, Fillia ; Sudborough, Ivan Hal (1989). "Sobre la minimización del ancho en diseños lineales". Matemáticas Aplicadas Discretas . 23 (3): 243–265. doi : 10.1016/0166-218X(89)90016-4 . MR 0996137.
^ Díaz, Josep; Petit, Jordi; Serna, Maria (septiembre de 2002). "Un estudio de problemas de diseño de grafos" (PDF) . ACM Computing Surveys . 34 (3): 313–356. doi :10.1145/568522.568523.
^ Seymour, Paul D. ; Thomas, Robin (1994). "Enrutamiento de llamadas y el cazador de ratas". Combinatorica . 14 (2): 217–241. doi :10.1007/BF01215352.
^ abc Djidjev, Hristo N.; Vrt'o, Imrich (2003). "Números cruzados y anchos de corte". Revista de algoritmos y aplicaciones de grafos . 7 (3): 245–251. doi : 10.7155/jgaa.00069 . MR 2112230.
^ Stöhr, Elena (1988). "Un equilibrio 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 . MR 0968104.
^ Yannakakis, Mihalis (1985). "Un algoritmo polinomial para la disposición lineal de árboles con corte mínimo". Revista de la ACM . 32 (4): 950–988. doi : 10.1145/4221.4228 . MR 0810346.
^ Monien, B.; Sudborough, IH (1988). "El corte mínimo es NP-completo para árboles ponderados por aristas". Ciencias Informáticas Teóricas . 58 (1–3): 209–229. doi : 10.1016/0304-3975(88)90028-X . MR 0963264.
^ Bodlaender, Hans L. ; Fomin, Fedor V.; Koster, Arie MCA; Kratsch, Dieter; Thilikos, Dimitrios M. (2012). "Una nota sobre algoritmos exactos para problemas de ordenación de vértices en grafos". Teoría de sistemas informáticos . 50 (3): 420–432. doi :10.1007/s00224-011-9312-0. hdl : 1956/4556 . MR 2885638. S2CID 9967521.
^ 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áticas Industriales y Aplicadas. págs. 1783–1793. arXiv : 1807.05209 . doi :10.1137/1.9781611975482.107. MR 3909576.
^ 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}}: CS1 maint: varios nombres: lista de autores ( enlace )
^ Fellows, Michael R. ; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances A. ; Saurabh, Saket (2008). "Problemas de diseño de grafos parametrizados por cobertura de vértices" (PDF) . En Hong, Seok-Hee ; Nagamochi, Hiroshi; Fukunaga, Takuro (eds.). Algorithms and Computation, 19.° Simposio Internacional, ISAAC 2008, Gold Coast, Australia, 15-17 de diciembre de 2008, Actas . Lecture Notes in Computer Science. Vol. 5369. Springer. págs. 294-305. doi :10.1007/978-3-540-92182-0_28.
^ 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". Programación matemática . 92 (1, Ser. A): 1–36. doi :10.1007/s101070100271. MR 1892295.
^ abc Wu, Yu; Austrin, Per; Pitassi, Toniann ; Liu, David (2014). "Inaproximabilidad del ancho del árbol, pebbling de una sola vez y problemas de diseño relacionados". Revista de investigación en inteligencia artificial . 49 : 569–600. doi : 10.1613/jair.4030 . MR 3195329.
^ Leighton, Tom ; Rao, Satish (1999). "Teoremas de flujo máximo y corte mínimo de múltiples productos básicos 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 . MR 1753034.
^ Arora, Sanjeev ; Rao, Satish ; Vazirani, Umesh (2009). "Flujos expansores, incrustaciones geométricas y particionamiento de grafos" (PDF) . Revista de la ACM . 56 (2): Art. 5, 37. doi :10.1145/1502793.1502794. MR 2535878.
^ Blin, Guillaume; Fertin, Guillaume; Hermelin, Danny; Vialette, Stéphane (2008). "Algoritmos de parámetros fijos para la búsqueda de similitud de proteínas bajo restricciones de estructura de ARNm". Journal of Discrete Algorithms . 6 (4): 618–626. doi : 10.1016/j.jda.2008.03.004 . MR 2463425.
^ Kayaaslan, Enver; Lambert, Thomas; Marchal, Loris; Uçar, Bora (2018). "Programación de gráficos de tareas en serie-paralelo para minimizar la memoria pico". Ciencias de la Computación Teórica . 707 : 1–23. doi : 10.1016/j.tcs.2017.09.037 . MR 3734396.
^ Fotouhi, Farshad; Pramanik, Sakti (1991). "El problema de optimizar el número de accesos a bloques al realizar uniones relacionales es NP-hard". Information Processing Letters . 38 (5): 271–275. doi :10.1016/0020-0190(91)90070-X. MR 1114421.
^ Morin, Pat ; Wood, David R. (2004). "Dibujos de gráficos tridimensionales de 1 curvatura". Revista de algoritmos y aplicaciones de grafos . 8 (3): 357–366. doi : 10.7155/jgaa.00095 . MR 2176967.