En teoría de grafos , una descomposición de trayectorias de un grafo G es, informalmente, una representación de G como un grafo de trayectorias "engrosado" , [1] y el ancho de trayectoria de G es un número que mide cuánto se engrosó la trayectoria para formar G. Más formalmente, una descomposición de trayectorias es una secuencia de subconjuntos de vértices de G de manera que los puntos finales de cada arista aparecen en uno de los subconjuntos y de manera que cada vértice aparece en una subsecuencia contigua de los subconjuntos, [2] y el ancho de trayectoria es uno menos que el tamaño del conjunto más grande en dicha descomposición. El ancho de trayectoria también se conoce como grosor de intervalo (uno menos que el tamaño máximo de camarilla en un supergrafo de intervalo de G ), número de separación de vértices o número de búsqueda de nodos . [3]
El ancho de ruta y las descomposiciones de ruta son estrechamente análogos al ancho de árbol y las descomposiciones de árbol . Desempeñan un papel clave en la teoría de los menores de grafos : las familias de grafos que están cerradas bajo los menores de grafos y no incluyen todos los bosques pueden caracterizarse por tener un ancho de ruta acotado, [2] y los "vórtices" que aparecen en la teoría de la estructura general para familias de grafos cerrados con menores tienen un ancho de ruta acotado. [4] El ancho de ruta y los grafos de ancho de ruta acotado también tienen aplicaciones en el diseño VLSI , el dibujo de grafos y la lingüística computacional .
Es NP-difícil encontrar el ancho de ruta de grafos arbitrarios, o incluso aproximarlo con precisión. [5] [6] Sin embargo, el problema es manejable con parámetros fijos : probar si un grafo tiene un ancho de ruta k se puede resolver en una cantidad de tiempo que depende linealmente del tamaño del grafo pero superexponencialmente de k . [7] Además, para varias clases especiales de grafos, como árboles , el ancho de ruta se puede calcular en tiempo polinomial sin dependencia de k . [8] [9] Muchos problemas en algoritmos de grafos se pueden resolver de manera eficiente en grafos de ancho de ruta acotado, utilizando programación dinámica en una descomposición de ruta del grafo. [10] La descomposición de ruta también se puede utilizar para medir la complejidad espacial de algoritmos de programación dinámica en grafos de ancho de árbol acotado . [11]
En el primero de su famosa serie de artículos sobre grafos menores , Neil Robertson y Paul Seymour (1983) definen una descomposición por trayectorias de un grafo G como una secuencia de subconjuntos Xi de vértices de G , con dos propiedades:
La segunda de estas dos propiedades es equivalente a exigir que los subconjuntos que contienen cualquier vértice particular formen una subsecuencia contigua de la secuencia completa. En el lenguaje de los artículos posteriores sobre la serie de grafos menores de Robertson y Seymour, una descomposición por trayectoria es una descomposición en árbol ( X , T ) en la que el árbol subyacente T de la descomposición es un grafo de trayectoria .
El ancho de una descomposición de ruta se define de la misma manera que para las descomposiciones de árbol, como max i | X i | − 1 , y el ancho de ruta de G es el ancho mínimo de cualquier descomposición de ruta de G . La resta de uno del tamaño de X i en esta definición hace poca diferencia en la mayoría de las aplicaciones del ancho de ruta, pero se utiliza para hacer que el ancho de ruta de un gráfico de ruta sea igual a uno.
Como describe Bodlaender (1998), el ancho de ruta se puede caracterizar de muchas maneras equivalentes.
Una descomposición de caminos puede describirse como una secuencia de grafos G i que se unen mediante la identificación de pares de vértices de grafos consecutivos en la secuencia, de modo que el resultado de realizar todas estas uniones es G . Los grafos G i pueden tomarse como los subgrafos inducidos de los conjuntos X i en la primera definición de descomposiciones de caminos, con dos vértices en subgrafos inducidos sucesivos que se unen cuando son inducidos por el mismo vértice en G , y en la otra dirección se pueden recuperar los conjuntos X i como los conjuntos de vértices de los grafos G i . El ancho de la descomposición de caminos es entonces uno menos que el número máximo de vértices en uno de los grafos G i . [2]
El ancho del camino de cualquier grafo G es igual a uno menos que el número de camarilla más pequeño de un grafo de intervalo que contiene a G como subgrafo. [12] Es decir, para cada descomposición de camino de G se puede encontrar un supergrafo de intervalo de G , y para cada supergrafo de intervalo de G se puede encontrar una descomposición de camino de G , tal que el ancho de la descomposición sea uno menos que el número de camarilla del grafo de intervalo.
En una dirección, supongamos que se da una descomposición de trayectorias de G. Entonces, se pueden representar los nodos de la descomposición como puntos en una línea (en orden de trayectorias) y representar cada vértice v como un intervalo cerrado que tiene estos puntos como puntos finales. De esta manera, los nodos de descomposición de trayectorias que contienen a v corresponden a los puntos representativos en el intervalo para v . El gráfico de intersección de los intervalos formados a partir de los vértices de G es un gráfico de intervalos que contiene a G como subgrafo. Sus camarillas máximas están dadas por los conjuntos de intervalos que contienen los puntos representativos, y su tamaño máximo de camarilla es uno más el ancho de trayectoria de G .
En la otra dirección, si G es un subgrafo de un grafo de intervalo con número de clique p + 1 , entonces G tiene una descomposición de ruta de ancho p cuyos nodos están dados por los cliques máximos del grafo de intervalo. Por ejemplo, el grafo de intervalo que se muestra con su representación de intervalo en la figura tiene una descomposición de ruta con cinco nodos, correspondientes a sus cinco cliques máximos ABC , ACD , CDE , CDF y FG ; el tamaño máximo de clique es tres y el ancho de esta descomposición de ruta es dos.
Esta equivalencia entre el ancho del camino y el espesor del intervalo es muy similar a la equivalencia entre el ancho del árbol y el número mínimo de clique (menos uno) de un grafo cordal del cual el grafo dado es un subgrafo. Los grafos de intervalo son un caso especial de grafos cordales, y los grafos de intervalo pueden representarse como grafos de intersección de subárboles de un árbol común, generalizando la forma en que los grafos de intervalo son grafos de intersección de subcaminos de un camino.
El número de separación de vértices de G con respecto a un ordenamiento lineal de los vértices de G es el número más pequeño s tal que, para cada vértice v , como máximo s vértices son anteriores a v en el ordenamiento pero que tienen v o un vértice posterior como vecino. El número de separación de vértices de G es el número de separación de vértices más pequeño de G con respecto a cualquier ordenamiento lineal de G . El número de separación de vértices fue definido por Ellis, Sudborough y Turner (1983), y es igual al ancho de camino de G . [13] Esto se desprende de la equivalencia anterior con los números de camarilla de grafos de intervalos: si G es un subgrafo de un grafo de intervalos I , representado (como en la figura) de tal manera que todos los puntos finales del intervalo son distintos, entonces el ordenamiento de los puntos finales izquierdos de los intervalos de I tiene un número de separación de vértices uno menos que el número de camarilla de I . Y en la otra dirección, a partir de un ordenamiento lineal de G se puede derivar una representación de intervalo en la que el punto extremo izquierdo del intervalo para un vértice v es su posición en el ordenamiento y el punto extremo derecho es la posición del vecino de v que viene último en el ordenamiento.
El juego de búsqueda de nodos en un grafo es una forma de persecución-evasión en la que un grupo de buscadores colabora para localizar a un fugitivo que se esconde en un grafo. Los buscadores se colocan en los vértices del grafo mientras que el fugitivo puede estar en cualquier borde del grafo, y la ubicación y los movimientos del fugitivo están ocultos para los buscadores. En cada turno, algunos o todos los buscadores pueden moverse (arbitrariamente, no necesariamente a lo largo de los bordes) de un vértice a otro, y luego el fugitivo puede moverse a lo largo de cualquier camino en el grafo que no pase por un vértice ocupado por el buscador. El fugitivo es atrapado cuando ambos puntos finales de su borde están ocupados por buscadores. El número de nodos de búsqueda de un grafo es el número mínimo de buscadores necesarios para garantizar que se puede garantizar que el fugitivo sea atrapado, sin importar cómo se mueva. Como muestran Kirousis y Papadimitriou (1985), el número de nodos de búsqueda de un grafo es igual a su espesor de intervalo. La estrategia óptima para los buscadores es moverlos de manera que en turnos sucesivos formen los conjuntos separadores de un ordenamiento lineal con un número mínimo de separación de vértices.
Cada grafo de n -vértices con ancho de camino k tiene como máximo k ( n − k + ( k − 1)/2) aristas, y los grafos de ancho de camino máximo k (grafos a los que no se pueden añadir más aristas sin aumentar el ancho de camino) tienen exactamente esta cantidad de aristas. Un grafo de ancho de camino máximo k debe ser un k -camino o una k -oruga, dos tipos especiales de k -árbol. Un k -árbol es un grafo cordal con exactamente n − k camarillas máximas , cada una de las cuales contiene k + 1 vértices; en un k -árbol que no es en sí mismo una ( k + 1) -camarilla, cada camarilla máxima separa el grafo en dos o más componentes, o contiene un único vértice de hoja, un vértice que pertenece a una única camarilla máxima. Un k -camino es un k -árbol con dos k -hojas como máximo , y una k -oruga es un k -árbol que se puede dividir en un k -camino y un conjunto de k -hojas, cada una adyacente a un k -clique separador del k -camino. En particular, los grafos máximos de ancho de camino uno son exactamente los árboles de oruga . [14]
Dado que las descomposiciones de rutas son un caso especial de descomposiciones de árboles, el ancho de ruta de cualquier grafo es mayor o igual que su ancho de árbol . El ancho de ruta también es menor o igual que el ancho de corte , el número mínimo de aristas que cruzan cualquier corte entre vértices de número inferior y de número superior en una disposición lineal óptima de los vértices de un grafo; esto se deduce porque el número de separación de vértices, el número de vértices de número inferior con vecinos de número superior, puede ser igual a lo sumo al número de aristas de corte. [15] Por razones similares, el ancho de corte es a lo sumo el ancho de ruta multiplicado por el grado máximo de los vértices en un grafo dado. [16]
Cualquier bosque de n -vértices tiene un ancho de ruta O (log n ) . [17] Porque, en un bosque, uno siempre puede encontrar un número constante de vértices cuya eliminación deja un bosque que puede ser dividido en dos subbosques más pequeños con a lo sumo 2 n ⁄ 3 vértices cada uno. Una disposición lineal formada al dividir recursivamente cada uno de estos dos subbosques, colocando los vértices separadores entre ellos, tiene un número de búsqueda de vértices logarítmico. La misma técnica, aplicada a una descomposición en árbol de un grafo, muestra que, si el ancho de árbol de un grafo de n -vértices G es t , entonces el ancho de ruta de G es O ( t log n ) . [18] Dado que los grafos externalplanares , los grafos serie-paralelos y los grafos de Halin tienen todos un ancho de árbol acotado, todos ellos también tienen a lo sumo un ancho de ruta logarítmico.
Además de sus relaciones con treewidth, pathwidth también está relacionado con clique-width y cutwidth , a través de gráficos de línea ; el gráfico de línea L ( G ) de un gráfico G tiene un vértice para cada arista de G y dos vértices en L ( G ) son adyacentes cuando las dos aristas correspondientes de G comparten un punto final. Cualquier familia de gráficos tiene pathwidth acotado si y solo si sus gráficos de línea tienen clique-width lineal acotado, donde clique-width lineal reemplaza la operación de unión disjunta de clique-width con la operación de adjuntar un único nuevo vértice. [19] Si un gráfico conectado con tres o más vértices tiene un grado máximo de tres, entonces su cutwidth es igual al número de separación de vértices de su gráfico de línea. [20]
En cualquier grafo planar , el ancho del camino es como máximo proporcional a la raíz cuadrada del número de vértices. [21] Una forma de encontrar una descomposición de caminos con este ancho es (de manera similar a la descomposición de caminos de ancho logarítmico de los bosques descrita anteriormente) usar el teorema del separador planar para encontrar un conjunto de O ( √ n ) vértices cuya eliminación separa el grafo en dos subgrafos de como máximo 2 n ⁄ 3 vértices cada uno, y concatenar descomposiciones de caminos construidas recursivamente para cada uno de estos dos subgrafos. La misma técnica se aplica a cualquier clase de grafos para los que se cumple un teorema del separador similar. [22] Dado que, al igual que los grafos planares, los grafos en cualquier familia de grafos cerrados menores fijos tienen separadores de tamaño O ( √ n ) , [23] se deduce que el ancho de camino de los grafos en cualquier familia cerrada menor fija es nuevamente O ( √ n ) . Para algunas clases de grafos planares, el ancho de camino del grafo y el ancho de camino de su grafo dual deben estar dentro de un factor constante uno del otro: se conocen límites de esta forma para grafos planos exteriores biconectados [24] y para grafos poliédricos. [25] Para grafos planares 2-conectados, el ancho de camino del grafo dual es menor que el ancho de camino del grafo lineal. [26] Queda abierto si el ancho de camino de un grafo planar y su dual están siempre dentro de un factor constante uno del otro en los casos restantes.
En algunas clases de gráficos, se ha demostrado que el ancho del camino y el ancho del árbol son siempre iguales entre sí: esto es cierto para los cografos , [27] los gráficos de permutación , [28] los complementos de los gráficos de comparabilidad , [29] y los gráficos de comparabilidad de órdenes de intervalo . [30]
En cualquier grafo cúbico , o más generalmente cualquier grafo con grado máximo de vértice tres, el ancho de camino es como máximo n ⁄ 6 + o( n ) , donde n es el número de vértices en el grafo. Existen grafos cúbicos con ancho de camino 0,082 n , pero no se sabe cómo reducir esta brecha entre este límite inferior y el límite superior n ⁄ 6 . [31]
Es NP-completo determinar si el ancho de ruta de un gráfico dado es como máximo k , cuando k es una variable dada como parte de la entrada. [5] Los límites de tiempo del peor caso más conocidos para calcular el ancho de ruta de gráficos arbitrarios de n vértices son de la forma O (2 n n c ) para alguna constante c . [32] Sin embargo, se conocen varios algoritmos para calcular descomposiciones de ruta de manera más eficiente cuando el ancho de ruta es pequeño, cuando la clase de gráficos de entrada es limitada o aproximadamente.
El ancho de ruta es manejable con parámetros fijos : para cualquier constante k , es posible probar si el ancho de ruta es como máximo k , y si es así, encontrar una descomposición de ruta de ancho k , en tiempo lineal. [7] En general, estos algoritmos operan en dos fases. En la primera fase, se utiliza la suposición de que el grafo tiene un ancho de ruta k para encontrar una descomposición de ruta o descomposición de árbol que no es óptima, pero cuyo ancho se puede acotar como una función de k . En la segunda fase, se aplica un algoritmo de programación dinámica a esta descomposición para encontrar la descomposición óptima. Sin embargo, los límites de tiempo para los algoritmos conocidos de este tipo son exponenciales en k 2 , poco prácticos excepto para los valores más pequeños de k . [33] Para el caso k = 2, de Fluiter (1997) proporciona un algoritmo explícito de tiempo lineal basado en una descomposición estructural de grafos de ancho de ruta 2.
Bodlaender (1994) examina la complejidad de calcular el ancho de ruta en varias clases especiales de grafos. Determinar si el ancho de ruta de un grafo G es como máximo k sigue siendo NP-completo cuando G se restringe a grafos de grado acotado, [34] grafos planares , [34] grafos planares de grado acotado, [34] grafos cordales , [35] dominós cordales, [36] los complementos de grafos de comparabilidad , [29] y grafos bipartitos hereditarios de distancia . [37] De ello se deduce inmediatamente que también es NP-completo para las familias de grafos que contienen los grafos bipartitos hereditarios de distancia, incluidos los grafos bipartitos, grafos bipartitos cordales, grafos hereditarios de distancia y grafos circulares . [37]
Sin embargo, el ancho de ruta se puede calcular en tiempo lineal para árboles y bosques. [9] También se puede calcular en tiempo polinomial para gráficos de ancho de árbol acotado, incluidos gráficos en serie-paralelos , gráficos planos exteriores y gráficos de Halin , [7] así como para gráficos divididos , [38] para los complementos de gráficos cordales, [39] para gráficos de permutación , [28] para cografos , [27] para gráficos de arco circular , [40] para los gráficos de comparabilidad de órdenes de intervalo, [30] y, por supuesto, para los propios gráficos de intervalo , ya que en ese caso el ancho de ruta es solo uno menos que el número máximo de intervalos que cubren cualquier punto en una representación de intervalo del gráfico.
Es NP-difícil aproximar el ancho de ruta de un grafo dentro de una constante aditiva. [6] La relación de aproximación más conocida de un algoritmo de aproximación de tiempo polinomial para el ancho de ruta es O ((log n ) 3/2 ) . [41] Para algoritmos de aproximación anteriores para el ancho de ruta, consulte Bodlaender et al. (1992) y Guha (2000). Para aproximaciones en clases restringidas de grafos, consulte Kloks y Bodlaender (1992).
Un menor de un grafo G es otro grafo formado a partir de G mediante la contracción de aristas, la eliminación de aristas y la eliminación de vértices. Los menores de grafos tienen una teoría profunda en la que varios resultados importantes involucran el ancho de la ruta.
Si una familia F de grafos está cerrada bajo la toma de menores (cada menor de un miembro de F también está en F ), entonces por el teorema de Robertson-Seymour F puede ser caracterizada como los grafos que no tienen ningún menor en X , donde X es un conjunto finito de menores prohibidos . [42] Por ejemplo, el teorema de Wagner establece que los grafos planares son los grafos que no tienen ni el grafo completo K 5 ni el grafo bipartito completo K 3,3 como menores. En muchos casos, las propiedades de F y las propiedades de X están estrechamente relacionadas, y el primer resultado de este tipo fue de Robertson & Seymour (1983), [2] y relaciona el ancho de camino acotado con la existencia de un bosque en la familia de menores prohibidos. Específicamente, defina una familia F de grafos como que tiene un ancho de camino acotado si existe una constante p tal que cada grafo en F tiene un ancho de camino como máximo p . Entonces, una familia F cerrada por menores tiene un ancho de ruta acotado si y solo si el conjunto X de menores prohibidos para F incluye al menos un bosque.
En una dirección, este resultado es fácil de demostrar: si X no incluye al menos un bosque, entonces los grafos libres de X no tienen un ancho de camino acotado. Porque, en este caso, los grafos libres de X incluyen todos los bosques, y en particular incluyen los árboles binarios perfectos . Pero un árbol binario perfecto con 2 k + 1 niveles tiene un ancho de camino k , por lo que en este caso los grafos libres de X tienen un ancho de camino ilimitado. En la otra dirección, si X contiene un bosque de n vértices, entonces los grafos libres de X tienen un ancho de camino como máximo n − 2. [ 43]
La propiedad de tener un ancho de camino de como máximo p es, en sí misma, cerrada bajo la consideración de menores: si G tiene una descomposición de caminos con un ancho de como máximo p , entonces la misma descomposición de caminos sigue siendo válida si se elimina cualquier arista de G , y cualquier vértice puede eliminarse de G y de su descomposición de caminos sin aumentar el ancho. La contracción de una arista, también, puede lograrse sin aumentar el ancho de la descomposición, fusionando los subcaminos que representan los dos puntos finales de la arista contraída. Por lo tanto, los grafos de ancho de camino de como máximo p pueden caracterizarse por un conjunto X p de menores excluidos. [42] [44]
Aunque X p necesariamente incluye al menos un bosque, no es cierto que todos los grafos en X p sean bosques: por ejemplo, X 1 consiste en dos grafos, un árbol de siete vértices y el triángulo K 3 . Sin embargo, el conjunto de árboles en X p puede ser caracterizado con precisión: estos árboles son exactamente los árboles que pueden formarse a partir de tres árboles en X p − 1 conectando un nuevo vértice raíz por una arista a un vértice elegido arbitrariamente en cada uno de los tres árboles más pequeños. Por ejemplo, el árbol de siete vértices en X 1 se forma de esta manera a partir del árbol de dos vértices (una sola arista) en X 0 . Con base en esta construcción, el número de menores prohibidos en X p puede demostrarse que es al menos ( p !) 2 . [44] Se ha calculado el conjunto completo X 2 de menores prohibidos para grafos de ancho de ruta 2; contiene 110 grafos diferentes. [45]
El teorema de la estructura de grafos para familias de grafos menores cerrados establece que, para cualquier familia F de este tipo , los grafos en F pueden descomponerse en sumas de clique de grafos que pueden incrustarse en superficies de género acotado , junto con un número acotado de vértices y vórtices para cada componente de la suma de clique. Un vértice es un vértice que puede ser adyacente a cualquier otro vértice en su componente, mientras que un vórtice es un grafo de ancho de camino acotado que está pegado en una de las caras de la incrustación de género acotado de un componente. El ordenamiento cíclico de los vértices alrededor de la cara en la que está incrustado un vórtice debe ser compatible con la descomposición del camino del vórtice, en el sentido de que romper el ciclo para formar un ordenamiento lineal debe conducir a un ordenamiento con un número de separación de vértices acotado. [4] Esta teoría, en la que el ancho de camino está íntimamente conectado a familias de grafos menores cerrados arbitrarias, tiene importantes aplicaciones algorítmicas. [46]
En el diseño VLSI , el problema de separación de vértices se estudió originalmente como una forma de dividir circuitos en subsistemas más pequeños, con una pequeña cantidad de componentes en el límite entre los subsistemas. [34]
Ohtsuki et al. (1979) utilizan el espesor de intervalo para modelar el número de pistas necesarias en un diseño unidimensional de un circuito VLSI, formado por un conjunto de módulos que necesitan ser interconectados por un sistema de redes. En su modelo, se forma un grafo en el que los vértices representan redes, y en el que dos vértices están conectados por una arista si sus redes se conectan ambas al mismo módulo; es decir, si los módulos y las redes se interpretan como formando los nodos y las hiperaristas de un hipergrafo entonces el grafo formado a partir de ellos es su grafo lineal . Una representación de intervalo de un supergrafo de este grafo lineal, junto con una coloración del supergrafo, describe una disposición de las redes a lo largo de un sistema de pistas horizontales (una pista por color) de tal manera que los módulos se pueden colocar a lo largo de las pistas en un orden lineal y conectarse a las redes apropiadas. El hecho de que los gráficos de intervalo sean gráficos perfectos [47] implica que el número de colores necesarios, en una disposición óptima de este tipo, es el mismo que el número de camarilla de la completitud del intervalo del gráfico neto.
El diseño de matriz de compuertas [48] es un estilo específico de diseño VLSI CMOS para circuitos lógicos booleanos . En los diseños de matriz de compuertas, las señales se propagan a lo largo de "líneas" (segmentos de línea verticales) mientras que cada compuerta del circuito está formada por una secuencia de características del dispositivo que se encuentran a lo largo de un segmento de línea horizontal. Por lo tanto, el segmento de línea horizontal para cada compuerta debe cruzar los segmentos verticales para cada una de las líneas que forman entradas o salidas de la compuerta. Al igual que en los diseños de Ohtsuki et al. (1979), un diseño de este tipo que minimiza el número de pistas verticales en las que se deben disponer las líneas se puede encontrar calculando el ancho de ruta de un gráfico que tiene las líneas como sus vértices y pares de líneas que comparten una compuerta como sus bordes. [49] El mismo enfoque algorítmico también se puede utilizar para modelar problemas de plegado en matrices lógicas programables . [50]
Pathwidth tiene varias aplicaciones para el dibujo de gráficos :
En la compilación de lenguajes de programación de alto nivel , el ancho de ruta surge en el problema de reordenar secuencias de código de línea recta (es decir, código sin ramas ni bucles de flujo de control ) de tal manera que todos los valores calculados en el código se puedan colocar en registros de máquina en lugar de tener que volcarse en la memoria principal. En esta aplicación, se representa el código que se va a compilar como un gráfico acíclico dirigido en el que los nodos representan los valores de entrada al código y los valores calculados por las operaciones dentro del código. Una arista del nodo x al nodo y en este DAG representa el hecho de que el valor x es una de las entradas a la operación y . Un ordenamiento topológico de los vértices de este DAG representa un reordenamiento válido del código, y el número de registros necesarios para evaluar el código en un ordenamiento dado está dado por el número de separación de vértices del ordenamiento. [55]
Para cualquier número fijo w de registros de máquina, es posible determinar en tiempo lineal si un fragmento de código de línea recta se puede reordenar de tal manera que se pueda evaluar con, como máximo, w registros. Porque, si el número de separación de vértices de un ordenamiento topológico es, como máximo , w , la separación mínima de vértices entre todos los ordenamientos no puede ser mayor, por lo que el grafo no dirigido formado ignorando las orientaciones del DAG descrito anteriormente debe tener un ancho de ruta como máximo w . Es posible probar si este es el caso, utilizando los algoritmos conocidos manejables con parámetros fijos para el ancho de ruta, y si es así, encontrar una descomposición de ruta para el grafo no dirigido, en tiempo lineal, dado el supuesto de que w es una constante. Una vez que se ha encontrado una descomposición de ruta, se puede encontrar un ordenamiento topológico de ancho w (si existe uno) utilizando programación dinámica, nuevamente en tiempo lineal. [55]
Kornai y Tuza (1992) describen una aplicación del ancho de ruta en el procesamiento del lenguaje natural . En esta aplicación, las oraciones se modelan como gráficos, en los que los vértices representan palabras y los bordes representan relaciones entre palabras; por ejemplo, si un adjetivo modifica a un sustantivo en la oración, entonces el gráfico tendría un borde entre esas dos palabras. Debido a la capacidad limitada de la memoria humana a corto plazo, [56] Kornai y Tuza argumentan que este gráfico debe tener un ancho de ruta acotado (más específicamente, argumentan, un ancho de ruta de como máximo seis), ya que de lo contrario los humanos no podrían analizar el habla correctamente.
Muchos problemas en algoritmos de grafos pueden resolverse eficientemente en grafos de ancho de ruta bajo, utilizando programación dinámica en una descomposición de ruta del grafo. [10] Por ejemplo, si se da un ordenamiento lineal de los vértices de un grafo G de n vértices, con un número de separación de vértices w , entonces es posible encontrar el conjunto independiente máximo de G en el tiempo O(2 w n ). [31] En grafos de ancho de ruta acotado, este enfoque conduce a algoritmos manejables con parámetros fijos, parametrizados por el ancho de ruta. [49] Tales resultados no se encuentran con frecuencia en la literatura porque están subsumidos por algoritmos similares parametrizados por el ancho de árbol; sin embargo, el ancho de ruta surge incluso en algoritmos de programación dinámica basados en el ancho de árbol al medir la complejidad espacial de estos algoritmos. [11]
El mismo método de programación dinámica también se puede aplicar a grafos con ancho de ruta ilimitado, lo que conduce a algoritmos que resuelven problemas de grafos no parametrizados en tiempo exponencial . Por ejemplo, la combinación de este enfoque de programación dinámica con el hecho de que los grafos cúbicos tienen un ancho de ruta n /6 + o( n ) muestra que, en un grafo cúbico, el conjunto independiente máximo se puede construir en tiempo O(2 n /6 + o( n ) ), más rápido que los métodos conocidos anteriormente. [31] Un enfoque similar conduce a algoritmos de tiempo exponencial mejorados para los problemas de corte máximo y conjunto dominante mínimo en grafos cúbicos, [31] y para varios otros problemas de optimización NP-hard. [57]
