Descomposición de ramas
De Wikipedia, la enciclopedia libre
  (Redirigido desde Branchwidth )
Saltar a navegación Saltar a búsqueda
Descomposición de ramas de un gráfico de cuadrícula , que muestra una separación electrónica. La separación, la descomposición y el gráfico tienen un ancho de tres.

En teoría de grafos , una descomposición de ramas de un grafo no dirigido G es un agrupamiento jerárquico de los bordes de G , representado por un árbol binario T sin raíces con los bordes de G como sus hojas. Al eliminar cualquier borde de T, los bordes de G se dividen en dos subgrafos, y el ancho de la descomposición es el número máximo de vértices compartidos de cualquier par de subgrafos formados de esta manera. El branchwidth de G es la anchura mínima de cualquier rama-descomposición de G .

El ancho de rama está estrechamente relacionado con el ancho del árbol : para todos los gráficos, ambos números están dentro de un factor constante el uno del otro, y ambas cantidades pueden caracterizarse por menores prohibidos . Y al igual que con el ancho de árbol, muchos problemas de optimización de gráficos pueden resolverse de manera eficiente para gráficos de ancho de rama pequeño. Sin embargo, a diferencia del ancho de árbol, el ancho de rama de los gráficos planos se puede calcular exactamente, en tiempo polinomial . Las descomposiciones de rama y el ancho de rama también se pueden generalizar de gráficos a matroides .

Definiciones

Un árbol binario sin raíz es un gráfico no dirigido y conectado sin ciclos en el que cada nodo no hoja tiene exactamente tres vecinos. Una descomposición de ramas puede estar representada por un árbol binario T sin raíces , junto con una biyección entre las hojas de T y los bordes del gráfico dado G  = ( V , E ). Si e es cualquier borde del árbol T , entonces quitar e de T lo divide en dos subárboles T 1 y T 2 . Esta partición de Ten subárboles induce una partición de los bordes asociados con las hojas de T en dos subgraphs G 1 y G 2 de G . Esta partición de G en dos subgrafos se denomina separación electrónica .

El ancho de una e-separación es el número de vértices de G que inciden tanto en un borde de E 1 como en un borde de E 2 ; es decir, es el número de vértices que comparten los dos subgrafos G 1 y G 2 . El ancho de la descomposición de la rama es el ancho máximo de cualquiera de sus e-separaciones. El branchwidth de G es la anchura mínima de una rama-descomposición de G .

Relación con el ancho del árbol

Las descomposiciones de las ramas de los gráficos están estrechamente relacionadas con las descomposiciones de los árboles , y el ancho de las ramas está estrechamente relacionado con el ancho del árbol : las dos cantidades están siempre dentro de un factor constante entre sí. En particular, en el artículo en el que introdujeron el ancho de rama, Neil Robertson y Paul Seymour [1] mostraron que para un gráfico G con ancho de árbol k y ancho de rama b > 1,

Ancho de talla

El ancho de talla es un concepto definido de manera similar al ancho de rama, excepto que los bordes se reemplazan por vértices y viceversa. Una descomposición de tallado es un árbol binario sin raíces en el que cada hoja representa un vértice en el gráfico original, y el ancho de un corte es el número (o el peso total en un gráfico ponderado) de los bordes que inciden en un vértice en ambos subárboles.

Los algoritmos de ancho de rama normalmente funcionan reduciendo a un problema de ancho de tallado equivalente. En particular, el ancho de talla del gráfico medial de un gráfico plano es exactamente el doble del ancho de la rama del gráfico original. [2]

Algoritmos y complejidad

Es NP-completo determinar si un gráfico G tiene una descomposición de ramas de ancho como máximo k , cuando tanto G como k se consideran entradas del problema. [2] Sin embargo, los gráficos con ancho de rama como máximo k forman una familia de gráficos menor-cerrada , [3] de lo que se deduce que calcular el ancho de rama es manejable con parámetros fijos : hay un algoritmo para calcular descomposiciones de rama óptimas cuya ejecución el tiempo, en gráficos de ancho de rama k para cualquier constante fija k , es lineal en el tamaño del gráfico de entrada. [4]

Para gráficos planos , el ancho de rama se puede calcular exactamente en tiempo polinomial. Esto contrasta con el ancho de árbol para el cual la complejidad de los gráficos planos es un problema abierto bien conocido. [5] El algoritmo original para ancho de rama plano, de Paul Seymour y Robin Thomas , tomó tiempo O ( n 2 ) en gráficos con n vértices, y su algoritmo para construir una descomposición de rama de este ancho tomó tiempo O ( n 4 ). [2] Esto se aceleró más tarde a O ( n 3 ). [6]

Al igual que con el ancho de árbol, el ancho de rama se puede utilizar como base de los algoritmos de programación dinámica para muchos problemas de optimización NP-hard, utilizando una cantidad de tiempo que es exponencial en el ancho del gráfico de entrada o matroide. [7] Por ejemplo, Cook y Seymour (2003) aplican programación dinámica basada en el ancho de rama a un problema de fusionar múltiples soluciones parciales al problema del viajante de comercio en una única solución global, formando un gráfico disperso a partir de la unión de las soluciones parciales, utilizando una heurística de agrupamiento espectral para encontrar una buena descomposición de ramas de este gráfico y aplicando programación dinámica a la descomposición. Fomin y Thilikos (2006) argumentan que el ancho de rama funciona mejor que el ancho de árbol en el desarrollo de algoritmos manejables con parámetros fijos en gráficos planos, por varias razones: el ancho de rama puede estar más limitado por una función del parámetro de interés que los límites del ancho de árbol, se puede calcular exactamente en tiempo polinomial en lugar de simplemente aproximado, y el algoritmo para calcularlo no tiene grandes constantes ocultas.

Generalización a matroides

También es posible definir una noción de descomposición de ramas para matroides que generaliza las descomposiciones de ramas de los gráficos. [8] Una descomposición de ramas de un matroide es un agrupamiento jerárquico de los elementos matroides, representados como un árbol binario sin raíces con los elementos del matroide en sus hojas. Un e-separación se puede definir de la misma manera que para los gráficos, y resulta en una partición del conjunto M de elementos matroid en dos subconjuntos A y B . Si ρ denota la función de rango de la matroide, entonces el ancho de una e-separación se define como ρ ( A ) + ρ ( B ) - ρ ( M ) + 1, y el ancho de la descomposición y el ancho de rama de la matroide se definen de forma análoga. El ancho de rama de un gráfico y el ancho de rama del matroide gráfico correspondiente pueden diferir: por ejemplo, el gráfico de ruta de tres bordes y la estrella de tres bordes tienen anchos de rama diferentes, 2 y 1 respectivamente, pero ambos inducen el mismo matroide gráfico con ancho de rama 1. [9] Sin embargo, para gráficos que no son árboles, el ancho de rama del gráfico es igual al ancho de rama de su matroide gráfico asociado. [10] El ancho de rama de un matroide es igual al ancho de rama de su matroide dual, y en particular esto implica que el ancho de rama de cualquier grafo plano que no sea un árbol es igual al de su dual. [9]

El ancho de rama es un componente importante de los intentos de extender la teoría de grafos menores a matroides menores : aunque el ancho de árbol también se puede generalizar a matroides, [11] y juega un papel más importante que el ancho de rama en la teoría de grafos menores, el ancho de rama tiene propiedades más convenientes en el entorno matroide. [12] Robertson y Seymour conjeturaron que las matroides representables sobre cualquier campo finito particular están bien cuasi-ordenadas , de manera análoga al teorema de Robertson-Seymour para gráficos, pero hasta ahora esto se ha probado solo para las matroides de ancho de rama acotado. [13]Además, si una familia menor cerrada de matroides representable sobre un campo finito no incluye las matroides gráficas de todos los gráficos planos, entonces hay un límite constante en el ancho de rama de las matroides de la familia, generalizando resultados similares para el gráfico menor cerrado. familias. [14]

Para cualquier constante fija k , las matroides con ancho de rama como máximo k pueden ser reconocidas en tiempo polinomial por un algoritmo que tiene acceso a la matroide a través de un oráculo de independencia . [15]

Menores prohibidos

Los cuatro menores prohibidos para gráficos de ancho de rama tres.

Según el teorema de Robertson-Seymour , las gráficas de ancho de rama k pueden caracterizarse por un conjunto finito de menores prohibidos . Los gráficos de ancho de rama 0 son las coincidencias ; los menores mínimos prohibidos son un gráfico de trayectoria de dos bordes y un gráfico de triángulo (o el ciclo de dos bordes, si se consideran gráficos múltiples en lugar de gráficos simples). [16] Los gráficos de branchwidth 1 son los gráficos en los que cada componente conectado es una estrella ; los menores mínimos prohibidos para el ancho de rama 1 son el gráfico de triángulo (o el ciclo de dos aristas, si se consideran gráficos múltiples en lugar de simples) y el gráfico de trayectoria de tres aristas. [dieciséis]Los gráficos de ancho de rama 2 son los gráficos en los que cada componente biconectado es un gráfico en serie-paralelo ; el único menor mínimo prohibido es el gráfico completo K 4 en cuatro vértices. [16] Un gráfico tiene un ancho de rama tres si y solo si tiene un ancho de árbol tres y no tiene el gráfico de cubo como menor; por lo tanto, los cuatro menores prohibidos mínimos son tres de los cuatro menores prohibidos para el ancho de árbol tres (el gráfico del octaedro , el gráfico completo K 5 y el gráfico de Wagner ) junto con el gráfico del cubo. [17]

Los menores prohibidos también se han estudiado para el ancho de rama matroide, a pesar de la falta de un análogo completo al teorema de Robertson-Seymour en este caso. Una matroide tiene un ancho de rama uno si y solo si cada elemento es un bucle o un coloop, por lo que el menor mínimo prohibido único es la matroide uniforme U (2,3), la matroide gráfica del gráfico triangular. Una matroid tiene branchwidth dos si y solo si es la matroid gráfica de una gráfica de branchwidth dos, por lo que sus menores prohibidos mínimos son la matroid gráfica de K 4y el matroide no gráfico U (2,4). Las matroides de ancho de rama tres no están bien cuasi-ordenadas sin el supuesto adicional de representabilidad sobre un campo finito, pero sin embargo las matroides con cualquier límite finito en su ancho de rama tienen un número finito de menores prohibidos mínimos, todos los cuales tienen un número de elementos que es como mucho exponencial en el ancho de rama. [18]

Notas

  1. ^ Robertson y Seymour 1991 , Teorema 5.1, p. 168.
  2. ↑ a b c Seymour y Thomas (1994) .
  3. ^ Robertson y Seymour (1991) , Teorema 4.1, p. 164.
  4. ^ Bodlaender y Thilikos (1997) . Fomin, Mazoit y Todinca (2009) describen un algoritmo con dependencia mejorada de k , (2 √ 3 ) k , a expensas de un aumento en la dependencia del número de vértices de lineal a cuadrático.
  5. ^ Kao, Ming-Yang, ed. (2008), "Treewidth of graphs", Enciclopedia de algoritmos , Springer, p. 969, ISBN 9780387307701, Otro problema abierto largo de pie es si hay un algoritmo de tiempo polinómico para computar la treewidth de grafos planos.
  6. ^ Gu y Tamaki (2008) .
  7. ^ Hicks (2000) ; Hliněný (2003) .
  8. ^ Robertson y Seymour 1991 . Sección 12, "Enredos y matroides", págs. 188-190.
  9. ↑ a b Mazoit y Thomassé (2007) .
  10. ^ Mazoit y Thomassé (2007) ; Hicks y McMurray (2007) .
  11. ^ Hliněný y Whittle (2006) .
  12. ^ Geelen, Gerards y Whittle (2006) .
  13. ^ Geelen, Gerards y Whittle (2002) ; Geelen, Gerards y Whittle (2006) .
  14. ^ Geelen, Gerards y Whittle (2006) ; Geelen, Gerards y Whittle (2007) .
  15. ^ Oum y Seymour (2007) .
  16. ↑ a b c Robertson y Seymour (1991) , Teorema 4.2, p. 165.
  17. ^ Bodlaender y Thilikos (1999) . El cuarto menor prohibido para el ancho de árbol tres, el prisma pentagonal, tiene el gráfico de cubo como menor, por lo que no es mínimo para el ancho de rama tres.
  18. ^ Hall y col. (2002) ; Geelen y col. (2003) .

Referencias

  • Bodlaender, Hans L .; Thilikos, Dimitrios M. (1997), "Algoritmos constructivos de tiempo lineal para ancho de rama", Proc. 24o Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP '97) , Lecture Notes in Computer Science, 1256 , Springer-Verlag, págs. 627–637, doi : 10.1007 / 3-540-63165-8_217 , hdl : 2117/96447.
  • Bodlaender, Hans L .; Thilikos, Dimitrios M. (1999), "Gráficos con ancho de rama como máximo tres", Journal of Algorithms , 32 (2): 167-194, doi : 10.1006 / jagm.1999.1011.
  • Cook, William; Seymour, Paul D. (2003), "Tour merging via branch-descomposition" (PDF) , INFORMS Journal on Computing , 15 (3): 233–248, doi : 10.1287 / ijoc.15.3.233.16078.
  • Fomin, Fedor V .; Thilikos, Dimitrios M. (2006), "Conjuntos dominantes en gráficos planos: ancho de rama y aceleración exponencial", SIAM Journal on Computing , 36 (2): 281, doi : 10.1137 / S0097539702419649.
  • Fomin, Fedor V .; Mazoit, Frédéric; Todinca, Ioan (2009), "Calcular el ancho de rama mediante triangulaciones y bloques eficientes" , Matemáticas aplicadas discretas , 157 (12): 2726-2736, doi : 10.1016 / j.dam.2008.08.009.
  • Geelen, Jim ; Gerards, Bert; Robertson, Neil ; Whittle, Geoff (2003), "Sobre los menores excluidos para las matroides de ancho de rama k ", Journal of Combinatorial Theory, Serie B , 88 (2): 261-265, doi : 10.1016 / S0095-8956 (02) 00046 -1.
  • Geelen, Jim ; Gerards, Bert; Whittle, Geoff (2002), "Branch-width and well-cuasi-ordering in matroids and graphs", Journal of Combinatorial Theory, Serie B , 84 (2): 270-290, doi : 10.1006 / jctb.2001.2082.
  • Geelen, Jim ; Gerards, Bert; Whittle, Geoff (2006), "Hacia una teoría de la estructura de matrices y matroides" (PDF) , Proc. Congreso Internacional de Matemáticos , III , págs. 827–842.
  • Geelen, Jim ; Gerards, Bert; Whittle, Geoff (2007), "Excluyendo un gráfico plano de las matroides representables por GF ( q )" (PDF) , Journal of Combinatorial Theory, Serie B , 97 (6): 971–998, doi : 10.1016 / j.jctb. 2007.02.005 , archivado desde el original (PDF) el 2010-09-24.
  • Gu, Qian-Ping; Tamaki, Hisao (julio de 2008), "Optimal branch-descomposition of planar graphs in O ( n 3 ) time", ACM Transactions on Algorithms , 4 (3): 30: 1–30: 13, doi : 10.1145 / 1367064.1367070.
  • Hall, Rhiannon; Oxley, James ; Semple, Charles; Whittle, Geoff (2002), "On matroids of branch-width three", Journal of Combinatorial Theory, Serie B , 86 (1): 148-171, doi : 10.1006 / jctb.2002.2120.
  • Hicks, Illya V. (2000), Descomposiciones de ramas y sus aplicaciones , Ph.D. tesis, Rice University, archivado desde el original el 16 de julio de 2011 , consultado el 6 de julio de 2010.
  • Hicks, Illya V .; McMurray, Nolan B., Jr. (2007), "El ancho de rama de los gráficos y sus matroides de ciclo", Journal of Combinatorial Theory, Serie B , 97 (5): 681–692, doi : 10.1016 / j.jctb.2006.12. 007.
  • Hliněný, Petr (2003), "Sobre propiedades matroides definibles en la lógica MSO", Proc. 28 ° Simposio Internacional sobre Fundamentos Matemáticos de la Informática (MFCS '03) , Lecture Notes in Computer Science, 2747 , Springer-Verlag, págs. 470–479, doi : 10.1007 / 978-3-540-45138-9 \ _41
  • Hliněný, Petr; Whittle, Geoff (2006), "Matroid tree-width" (PDF) , European Journal of Combinatorics , 27 (7): 1117–1128, doi : 10.1016 / j.ejc.2006.06.005 , archivado desde el original (PDF) el 2012-03-06 , consultado el 2010-07-06.
    • Addendum y corrigendum: Hliněný, Petr; Whittle, Geoff (2009), "Addendum to matroid tree-width", European Journal of Combinatorics , 30 (4): 1036–1044, doi : 10.1016 / j.ejc.2008.09.028.
  • Mazoit, Frédéric; Thomassé, Stéphan (2007), "Branchwidth of graphic matroids", en Hilton, Anthony; Talbot, John (eds.), Surveys in Combinatorics 2007 (PDF) , London Mathematical Society Lecture Note Series, 346 , Cambridge University Press, p. 275.
  • Oum, Sang-il ; Seymour, Paul (2007), "Testing branch-width", Journal of Combinatorial Theory , Serie B, 97 (3): 385–393, doi : 10.1016 / j.jctb.2006.06.006 , MR  2305892.
  • Robertson, Neil ; Seymour, Paul D. (1991), "Graph minors. X. Obstructions to tree-descomposition", Journal of Combinatorial Theory , 52 (2): 153-190, doi : 10.1016 / 0095-8956 (91) 90061-N.
  • Seymour, Paul D .; Thomas, Robin (1994), "Enrutamiento de llamadas y el cazador de ratas", Combinatorica , 14 (2): 217–241, doi : 10.1007 / BF01215352.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Branch-decomposition&oldid=1016711517 "
Contribute a better translation