Largura de caminho

Em teoria dos grafos, uma decomposição em caminho de um grafo G é, informalmente, uma representação de G como um caminho "alargado", e o pathwidth ou largura de caminho de G é um número que mede quanto o caminho foi ampliado em largura a partir de G. Mais formalmente, decomposição em caminho é uma sequência de subconjuntos de vértices de G em que os nós extremos de cada aresta apareçam em um dos subconjuntos e que cada vértice apareça em uma subsequência adjacente dos subconjuntos, e a largura de caminho é um a menos que o tamanho do maior conjunto em dada decomposição. Largura de caminho é também conhecida como largura de intervalo (um a menos que o tamanho do clique máximo em um supergrafo de intervalo de G), número de separação de vértice, ou número de busca de nós.

Largura de caminho e decomposições em caminho são aproximadamente análogos a largura de árvore e decomposição em árvores. Têm um papel fundamental na teoria de menores de grafos: as famílias de grafos que são fechadas sob menores de grafos e não incluem todas florestas devem ser caracterizadas como tendo caminhos de largura delimitados, e os "vórtices" aparecendo na teoria geral de estrutura para famílias fechadas sob menores de grafos tem caminhos de largura delimitados. Largura de caminho, e grafos de largura de caminho delimitados, possuem também aplicações em design de VLSI, desenho de grafos, and linguística computacional.

É NP-difícil encontrar a largura de caminho de grafos arbitrários, ou até mesmo fazer uma aproximação precisa. De qualquer maneira, o problema é tratável por parâmetro fixo: testando se um grafo de largura de caminho k pode ser resolvido em uma quantidade de tempo que depende linearmente do tamanho do grafo mas super-exponencialmente em k. Além disso, para várias classes especiais de grafos, como árvores, a largura de caminho pode ser computada em tempo polinomial sem dependência em k. Muitos problemas em algoritmos de grafos podem ser resolvidos eficientemente em grafos de largura de caminho delimitados, usando programação dinâmica em uma decomposição em caminho do grafo. Decomposição em caminho pode também ser usada para medir complexidade de espaço de algoritmos de programação dinâmica em grafos de largura de árvore.

Definição

No primeiro de sua famosa série de artigos sobre menores de grafos, Neil Robertson e Paul Seymour definiram a decomposição em caminho de um grafo G ser uma sequência de subconjuntos de X_i de vértices de G, com duas propriedades:

1. Para cada aresta de G, existe um i tal que ambos extremos (vértices) da aresta pertencem ao subconjuntoX_i; e
2. Para cada três índices i ≤ j ≤ k, X_i ∩ X_k ⊆ X_j.

A segunda dessas propriedades é equivalente a requerer que os subconjuntos contendo quaisquer vértices específicos formem uma subsequência adjacente da sequência inteira. Nas definições encontradas nos últimos artigos sobre menores de grafos de Robertson e Seymour, uma decomposição em caminho é uma decomposição em árvore (X,T) em que a árvore subjacente T da decomposição é um caminho.

A largura de uma decomposição em caminho é definida da mesma maneira que é para uma decomposição em árvore, como max_i |X_i| − 1, e a largura de caminho de G é a largura mínima de quaisquer decomposições em caminho de G. A subtração de 1 do tamanho de X_i nessa definição faz pouca diferença na maioria da aplicações de largura de caminho, mas é usada para estabelecer a largura de caminho de um grafo caminho sendo igual a um.

Caracterizações alternativas

Como Bodlaender (1998) descreve, largura de caminho pode ser caracterizada de várias maneiras equivalentes.

Sequências de colagem

Uma decomposição em caminho pode ser descrita com uma sequência de grafos G_i que são "colados" juntos identificando pares de vértices de grafos consecutivos na sequência. de modo que o resultado da execução de todas essas colagens é G. Os grafos G_i devem ser considerados como os subgrafos induzidos por vértice dos conjuntos X_i na primeira definição das decomposições em caminho, com dois vértices em sucessivos subgrafos induzidos em serem colados conjuntamente quando eles são induzidos pelo mesmo vértice em G, e em outra direção pode-se recuperar os conjuntos X_i como os conjuntos de nós dos grafos G_i. A largura da decomposição em caminho é então um menor que o número máximo de vértices em um dos grafos G_i.

Largura de intervalo

Um grafo de intervalos com largura de caminho dois, um menor que a cardinalidade de seus quatro cliques máximos ABC, ACD, CDE, and CDF.

A largura de caminho de qualquer grafo G é igual a um a menos que a quantidade dos menores cliques de um grafo de intervalos que contém G como subgrafo. Isto é, para cada decomposição em caminho de G pode-se procurar um super-grafo de intervalos de G, e para cada super-grafo de intervalos pode-se encontrar uma decomposição em caminho de G, tanto que a largura da decomposição seja uma menor que o numero de cliques do grafo de intervalos.

Por um lado, supondo que uma decomposição em caminho de G é dada. Então é possível representar os nó da decomposição como pontos em uma linha (em forma de um caminho) e representar cada vértice v como um intervalo fechado contendo esses pontos como extremos. Logo, os nós da decomposição em caminho compreendendo v correspondem aos pontos representativos no intervalo para v. O grafo de interseção dos intervalos formados dos vértices de G é um grafo de intervalos que engloba G como um subgrafo. Seus cliques máximos são dados pelos conjuntos de intervalos contendo os pontos representativos, e o tamanho do seu clique máximo é um mais a largura de caminho de G.

Por outro lado, se G é um subgrafo de um grafo de intervalos com número de cliques p + 1, então G tem uma decomposição em caminho com largura p, tal que seus nós são dados pelos cliques máximos do grafo de intervalos. Para exemplo, o gráfico de intervalos mostrado com sua representação de intervalos na figura ao lado tem uma decomposição em caminho com cinco nós, correspondendo aos seus cinco cliques máximos ABC, ACD, CDE, CDF, and FG; o tamanho do clique máximo é três e a largura dessa decomposição em caminho é dois.

Esta equivalência entre a largura de caminho e a largura de intervalo é aproximadamente análoga à equivalência entre largura de árvore e número de cliques mínimos (menos um) de um grafo cordal de que dado grafo é um subgrafo. Grafos de intervalos são um caso especial de grafos cordais, e grafos cordais podem ser representado como grafos de interseção de subárvores de uma árvore comum generalizando o modo que os grafos de intervalos são grafos de interseção de sub-caminho de um caminho.

Número de separação de vértices

Supondo que os vértices de um grafo G são linearmente ordenados, então o número de separação de vértices de G é o menor número s que, para cada vértice v, no máximo s vértices são anteriores a v na ordenação mas que tem v ou um vértice posterior como vizinho.

O número de separação de vértices de G é o número de separação de vértices mínimo de quaisquer ordenações lineares de G. O número de separação de vértices foi definido por Ellis, Sudborough & Turner (1983), e é igual à largura de caminho de G. Isso resulta da correspondência anterior com números de cliques em grafos de intervalos: se G é um subgrafo de um grafo de intervalos I, representado (como na figura) de modo que todos os nós extremos dos intervalos são distintos, então a ordenação dos nós extremos da esquerda do intervalo de I têm número de separação de vértices um menor que o número de cliques de I. E, por outro lado, a partir de uma ordenação linear de G, é praticável a derivação de uma representação de intervalos de modo que o extremo esquerdo de um intervalo para um vértice v esteja em sua posição na ordenação em ao extremo direito está a posição do vizinho de v que vem por último na ordenação.

Número de busca de nós

O jogo de busca de nós em um grafo é uma forma de perseguição e fuga, no qual um conjunto de investigadores colaboram para rastrear um fugitivo escondido em um grafo. Os rastreadores estão dispostos em vértices do grafo enquanto o fugitivo podem estar em qualquer aresta do grafo, e a localização do fugitivo e seus movimentos são ocultados dos investigadores. A cada turno, alguns ou todos os rastreadores podem se mover (arbitrariamente, não necessariamente ao longo das arestas) de um vértice a outro, e, então, o fugitivo tem o poder de se movimentar por qualquer caminho no grafo que não passe por um vértice ocupado por um investigador. O fugitivo é pego quando ambos extremos de sua aresta estão tomados por rastreadores. O número de busca de nós de um grafo é o número mínimo de rastreadores necessários para assegurar que haja a garantia de o fugitivo ser pego, independente de seu movimento. Como Kirousis & Papadimitriou (1985) mostram, o número de busca de nós de um grafo é igual a sua largura de intervalo. A estratégia ótima para rastreadores é se movimentar de maneira em que em sucessivos turnos formem os conjuntos de separação de uma ordenação linear com número mínimo de vértices.

Limitantes

Uma árvore centopeia (grafo), um grafo máximo com largura de caminho um.

Todo grafo de n-vértices com largura de caminho k tem no máximo k(n − k + (k − 1)/2)) arestas, e os grafos máximos com largura de caminho k (grafos aos quais não podem ser adicionados mais arestas sem que se aumente a largura de caminho) têm exatamente este número de arestas. Um grafo máximo de largura de caminho k deve ser ou um k-caminho ou um k-centopeia (caterpillar), dois tipos especiais de k-árvore. Uma k-árvore é um grafo cordal com exatamente n − k cliques máximos, cada um contendo k + 1 vértices; em uma k-árvore que não é um (k + 1)-clique por si só, cada clique máximo ou separa o grafo em dois ou mais componentes, ou contém um único vértice como folha (vértice de grau um), um vértice que pertence a apenas um único clique máximo). Um k-caminho é uma k-árvore com no máximo duas folhas, e uma k-centopeia é uma k-árvore que pode ser particionada em um k-caminho e um conjunto de k-folhas adjecentes a um k-clique separador do k-caminho. Em particular, os grafos máximo de largura da caminho um são exatamente as árvores centopeia.

Como decomposições em caminho são casos especiais de decomposições em árvores, a largura de caminho de qualquer grafo é maio ou igual a sua largura de árvore. A largura de caminho é também menor ou igual à largura de corte, o número mínimo de arestas que cruzam quaisquer cortes entre os vértice menor-numerados e os maior-numerados em um arranjo linear ótimo dos vértice de um grafo; isto acontece porque o número de separação de vértices, o número de vértices menor-numerados com vizinhos maior-numerados, pode no máximo ser igual ao número de arestas cortadas. Por razões similares, a largura de corte é no máximo a largura de caminho vezes o grau máximo dos vértices em um grafo dado.

Quaisquer florestas n-vértices tem uma largura de caminho O(log n). Pois, em uma floresta, é sempre possível encontrar um número constante de vértices cuja remoção deixa ser particionada em suas subflorestas menores com no máximo 2n/3 vértices cada. Um arranjo linear formado por particionar recursivamente cada uma dessas duas subflorestas, colocando os vértices separados entre elas, tem um número de busca de vértices logarítmico. A mesma técnica, aplicada à decomposição em árvore de um gráfico, mostra que, se a largura de árvore de um grafo n-vértices G é t, então a largura de caminho de G é O(t log n). Como grafos planares exteriores, grafos série-paralelos e grafos de Halin possuem todos larguras de árvore limitadas, e têm no máximo largura de caminho logarítmica.

Assim como suas relações com largura de árvore, largura de caminho é também relacionada à largura de clique e largura de corte, por meio de grafos linha; o grafo linha L(G) de um grafo G tem um vértice para cada aresta de G e dois vértices em L(G) são adjacentes quando as arestas correspondentes de G compartilham um nó extremo. Toda família de grafos tem largura de caminho limitada se e somente se seus grafos linha têm largura de clique linear limitada, onde a largura de clique linear substitui a operação de união disjunta da largura de clique com a operação de fazer adjacentes um único vértice novo. Se um grafo conexo com três ou mais vértices tem no máximo grau três, então sua largura de corte é igual ao número de separação de vértices de seu grafo linha.

Em todo grafo planar, a largura de caminho é no máximo proporcional à raiz quadrada do número de vértices. Um modo de encontrar uma decomposição em caminho com sua largura é (similarmente à decomposição em caminho de largura logarítmica de florestas descritas acima) para usar o teorema separador planar para encontrar um conjunto de O(√n) vértices cuja remoção separa o grafo em dois subgrafos de no máximo 2n/3 vértices cada, e concatenar decomposições em caminho recursivamente construídas para cada um desses dois subgrafos. A mesma técnica se aplica a qualquer classe de grafos para a qual um teorema separador seja válido. Portanto, assim como grafos planares, os grafos em qualquer família de grafos menor-fechados fixas tem separadores de tamanho O(√n), resultando em que a largura de caminho dos grafos em quaisquer família menor-fechada fixa é novamente O(√n). Para algumas classes de grafos planares, a largura de caminho do grafo e a largura de caminho de seu grafo dual deve estar entre um fator constante entre um e o outro: limites desta forma são conhecidos pro grafos planares exteriores bi-conectados e para grafos poliédricos. Para grafos planares bi-conectados, a largura de caminho do grafo dual é menor que a largura de caminho do grafo linha. Permanece aberta a questão de se a largura de caminho de um grafo planar e seu dual estão sempre dentro um fator constante um do outro nos casos restantes.

Em algumas classes de grafos, é provado que a largura de caminho e a largura de árvore são sempre iguais ao outro: isto é verdade para co-grafos, grafos de permutação, os complementos de grafos de comparabilidade e os grafos de comparabilidade de ordens de intervalo.

Em todo grafo cúbico, ou mais genericamente qualquer grafo com grau de vértices máximo igual a três, a largura de caminho é no máximo n/6 + o(n), onde n é o número de vértices no grafo. Há grafos cúbicos com largura de caminho 0.082n, mas não é conhecido como reduzir esta lacuna entre esse minorante e o majorante n/6.

Computando decomposições em caminho

É NP-completo determinar se a largura de caminho de um dado grafo é no máximo k, quando k é uma variável dada como parte da entrada. Os melhores limites de tempos em pior caso conhecidos para computar a largura de caminho de grafos n-vértices arbitrários são da forma O(2ⁿ n^c) para alguma constante c. Mesmo assim, diversos algoritmos são conhecidos para computar decomposições em caminho mais eficientemente quando a largura de caminho é pequena, quando a classe de grafos de entrada é limitada, ou aproximadamente.

Tratabilidade por parâmetro fixo

Largura de caminho é Pathwidth is tratável por parâmetro fixo: para qualquer constante k, é possível testar se a largura de caminho é no máximo k, e se for, encontrar uma decomposição em caminho de largura k, em tempo linear. Em geral, esses algoritmos operam em duas fases. Na primeira fase, a suposição que o grafo tem largura de caminho k é usada para achar uma decomposição em caminho ou decomposição em árvore que não é ótima, porém que sua largura pode ser limitada como uma função de k. Na segunda fase, um algoritmo em programação dinâmica é aplicado a esta decomposição com o objetivo de encontrar a decomposição ótima. De qualquer maneira, os limites de tempo para algoritmos conhecidos deste tipo são exponenciais em k², impraticáveis exceto para os menores valores de k. Para o caso k = 2 um algoritmo em tempo linear baseado na decomposição estrutural de grafos de largura de caminho dois é dado por de Fluiter (1997).

Classes especiais de grafos

Bodlaender (1994) pesquisa a complexidade de computar a largura de caminho em várias classes especiais de grafos. Determinando se a largura de caminho de um grafo G é no máximo k permanece NP-completo quando G é restrito a grafos de grau limitado, grafos planares, grafos planares de grau limitado, grafos cordais, dominós cordais, os complementos de grafos de comparabilidade, e grafos de distância hereditária bipartidos. Isso resulta em que é também NP-completo para as famílias de grafo que contém os grafos de distância hereditária, incluindo grafos bipartidos, grafos bipartidos cordais e grafos círculo.

De qualquer maneira, a largura de caminho pode ser computada em tempo linear para árvores e florestas. Deve ser, também, computável em tempo polinomial para grafos de largura de árvore limitada incluindo grafos série-paralelo, grafos planares externos, e grafos de Halin, assim como para grafos de divisão, para os complementos de grafos cordais, para grafos de permutação, para co-grafos, para grafos de arco circular, para os grafos de comparabilidade de ordens de intervalos, e, lógico, para os próprios grafos de intervalos, pois neste caso a largura de caminho é apenas um menor que o número máximo de intervalos cobrindo todo ponto em uma representação de intervalo do grafo.

Algoritmos de aproximação

É NP-difícil aproximar a largura de caminho de um grafo para dentro de uma constante aditiva. A melhor taxa de aproximação conhecida de um algoritmo de aproximação em tempo polinomial é O((log n)^3/2). Para algoritmos de aproximação anteriores para largura de caminho, veja Bodlaender et al. (1992) e Guha (2000). Para aproximaçãoes em classes de grafos restritas, veja Kloks & Bodlaender (1992).

Menores de Grafo

Um menor de um grafo G é outro grafo formado a partir de G por meio de contração e remoção de arestas, e remoção de vértices. Grafos menores possuem uma teoria profunda em que diversos resultados envolvem largura de caminho.

Excluindo uma floresta

Se uma família F de grafos é fechada sob a operação de gerar menores de grafos (todo menor de um membro de F está também em F), então pelo Teorema de Robertson–Seymour F pode ser caracterizada com os grafos que não tem nenhum menor em X, onde X é um conjunto finito de menores de grafo proibidos. Por exemplo, o teorema de Wagner constata que os grafos planares são os grafos que nem possuem o grafo completo K₅ nem o grafo bipartido completo K_3,3 como menores. Em vários casos, as propriedades de F e as propriedades de X são proximamente relacionadas, e a primeira que resulta deste tipo foi por Robertson & Seymour (1983), e se refere à relação entre largura de caminho limitada com a existência de uma floresta na família de grafos menores proibidos. Especificamente, define uma família F de grafos ter largura de caminho limitada se existe uma constante p que para cada grafo em F tem largura de caminho no máximo p. Então, uma família de menores-fechada F tem largura de caminho limitada se e somente se o conjunto X de grafos menores proibidos para F inclui no mínimo uma floresta.

Por outro lado, esse resultado é uma trivial para provar: se X não inclui ao menos uma floresta, então os grafos de X-livres-de-menor não tem largura de caminho limitada. Pois, neste caso, os grafos de X-livres-de-menor incluem todas as florestas, e em particular eles incluem as árvores binárias perfeitas. Mas uma árvore binária perfeita com 2k + 1 níveis tem uma largura de caminho k, então neste caso os grafos de X-livres-de-menor tem largura de caminho ilimitada. Na outra direção, se X contém uma floresta de n-vértices, então os grafos de X-livres-de-menor tem largura de caminho no máximo n − 2.

Obstruções à largura de caminho limitada

Os grafos menores proibidos para grafos de largura de caminho um.

A propriedade de ter largura de caminho no máximo p é, por si só, fechada sob a operação de gerar menores: se G tem uma decomposição em caminho com largura máxima p, então a mesma decomposição em caminho continua válida se alguma aresta é removida de G, e qualquer vértice pode ser removido de G e de suas decomposições em caminho sem aumentar sua largura. Contração de uma aresta pode, também, ser realizada sem aumentar a largura da decomposição, fundindo os sub-caminhos representando os dois nós extremos da aresta a ser contraída. Por esses motivos, os grafos de largura de caminho no máximo p podem ser descritos por um conjunto X_p de grafos menores excluídos.

Apesar de X_p necessariamente incluir no mínimo uma floresta, não é verdade que todos os grafos em X_p são florestas: por exemplo, X₁ consiste de dois grafos, uma árvore com sete vértices e o triângulo K₃. Entretanto, o conjunto de árvores em X_p pode ser precisamente descrito: estas árvores são exatamente as árvores que são formadas das três árvores em X_p − 1 através da conexão de um novo vértice raiz por uma aresta a um vértice arbitrariamente escolhido em cada uma das três árvores menores. Como exemplo, a árvore de sete vértices em X₁ é formada desta maneira a partir de uma árvore de dois vértices (uma aresta única) em X₀. Baseando-se nessa construção, o número de grafos menores proibidos em X_p pode ser mostrado como sendo no mínimo (p!)². O conjunto completo X₂ de grafos menores proibidos para grafos de largura de caminho dois foi computado; contém 110 grafos diferentes

Teoria da estrutura de grafos

O teorema da estrutura de grafos para famílias de grafos menores-fechados constata que, para qualquer família F, os grafos em F podem ser decompostos em soma de grafos que podem ser embutidos em superfícies de géneros limitados, unidos a um número de apexes e vórtices para cada componente da soma de cliques. Um apex é um vértice que pode ser adjacente a qualquer outro vértice em sua componente, enquanto um vórtex é um grafo de largura de caminho limitada que está "colado" a uma das faces da incorporação de género limitado de uma componente. A ordenação cíclica dos vértice em torno da face em que o vórtex está incorporado deve ser compatível com a decomposição em caminho do vórtex, no sentido em que quebrando o ciclo para formar uma ordenação linear deve encaminhar a uma ordenação com número de separação de vértices limitado. Esta teoria, em que a largura de caminho é intimamente conectada a famílias arbitrárias de grafos menores-fechados, tem importantes aplicações algorítmicas.

Aplicações

VLSI

Em arquitetura de VLSI, o problema de separação de vértices foi originalmente estudado como uma maneira de particionar circuitos em subsistemas menores, com um pequeno número de componentes nas fronteiras entre os subsistemas.

Ohtsuki et al. (1979) usa largura de intervalo para modelar o número de faixas necessárias em um layout de um circuito VLSI de unidimensional, formado por um conjunto de módulos que precisam estar interconectados por um sistema de redes. Em seu modelo, é gerado um grafo em que os vértices representam redes, e no qual dois vértices são conectados por uma aresta se ambas redes conectam ao mesmo módulo; ou seja, se os módulos e redes são interpretados como se formassem os nós e superarestas de um hipergrafo então o grafo formado a partir deles é seu grafo linha. Uma representação de intervalo de um supergrafo deste grafo linha, unido com uma coloração do supergrafo, descreve um arranjo das redes ao longo do sistema de faixas horizontais (uma faixa por cor) de modos que os módulos possam ser dispostos ao longo das faixas em ordem linear e conectar às redes apropriadas. O fato de que os grafos intervalos são grafos perfeitos implica que o número de cores necessárias, em um arranjo ótimo deste tipo, é o mesmo que o número de cliques da conclusão de intervalos do grafo de redes.

Layout de matriz de portas é um estilo específico de layout de VLSI CMOS para circuitos de lógica booleana. Nos layouts de matriz de portas, sinais são propagado por "linhas" (segmentos de linhas verticais) enquanto cada porta do circuito é formada por uma sequência de recursos de dispositivos que permanecem dispostos ao longo de um segmento de linha horizontal. Assim, o segmento de linha horizontal para cada porta deve cruzar os segmentos verticais para cada uma das linhas que formam entradas ou saídas da porta. Como nos layouts de Ohtsuki et al. (1979), um layout deste tipo que minimize o número de faixas verticais nas quais as linhas que estão a ser organizadas pode ser encontrado computando a largura de caminho de um grafo que possui as linhas como seus vértices e os pares de linhas compartilhando uma porta como suas arestas. A mesma abordagem algorítmica pode também ser usada para modelar problemas de reorganização (folding problems) em arrays lógicos programáveis.

Desenho de grafos

Largura de caminho tem diversas aplicações para desenho de grafos:

• Os grafos mínimos que possuem um dado número de cruzamento tem largura de caminho que é limitada por uma função de seu número de cruzamento.
• O número de linhas paralelas nas quais os vértices de uma árvore podem ser desenhados sem cruzamento de arestas (sob várias restrições naturais nas maneiras que vértices adjacentes podem ser colocados com respeito à sequência de linhas) é proporcional à largura de caminho da árvore.
• Um k-cruzamento de desenho de h-camadas de um grafo G é o posicionamento dos vértices de G em h linhas horizontais distintas, com arestas indicadas como caminhos poligonais monotônicos entre estas linhas, de modo que há no máximo k cruzamentos. Os grafos com tais desenhos têm largura de caminho que é limitada por uma função de h e k. Entretanto, quando h e k são ambos constantes, é possível, em tempo linear, determinar se um grafo tem um k-cruzamento com desenhor em h-camadas.
• Um grafo com n vértices e uma largura de caminho p pode ser incorporados a uma grade tridimensional de tamanho p × p × n de mode que não há duas arestas (representas como segmentos de linhas entre os pontos da grade) intersectem entre si. Assim, grafos de largura de caminho limitada têm incorporações de seu tipo com volume linear.

Construção de compiladores

Na compilação de linguagens de programação de alto nível, largura de caminho se torna notável no problema de reordenação de sequências de código de "linha direta" (isto é, código sem ramos ou loops de fluxo de controle) de modo que todos os valores computados no código podem ser colocados em registradores em vez de terem que ser "empurrados" para a memória principal. Nesta aplicação, representa-se o código a ser compilado como um grafo acíclico dirigido no qual os nós representam os valores de entrada do código e os valores computados pelas operações dentro do código. Uma aresta de um nó x par um nó y neste grafo representa o fato que o valor x é uma das entradas da operação y. Uma ordenação topológica dos vértices deste grafo acíclico dirigido representa uma ordenação válida do código, e o número de registradores necessários para avaliar o código em uma dada ordenação é dado pelo número de separação de vértices da ordenação.

Para qualquer número fixo w de registradores, é possível determinar em tempo linear se um trecho de código "linha-direta" (straight-line code) pode ser reordenado de modo que possa ser avaliado com no máximo w registradores. Pois, se o número de separação de vértices de uma ordenação topológica é no máximo w, a separação de vértices mínima entre todas as ordenações não pode ser maior, então o grafo não direcionado formado por ignorar as orientações do grafo acíclico dirigido descrito acima deve ter no máximo largura de caminho w. É possível testar se este é o caso, usando os conhecidos algoritmos tratáveis por parâmetro fixo para largura de caminho, e se for, para encontrar uma decomposição em caminho do grafo não direcionado, em tempo linear, dada a suposição de que w é uma constante. Uma vez que a decomposição em caminho for encontrada, uma ordenação topológica de largura w (se existir) pode ser encontrada usando programação dinâmica, novamente em tempo linear.

Linguística

Kornai & Tuza (1992) descrevem uma aplicação da largura de caminho em processamento de linguagem natural. Nesta aplicação, sentenças são modeladas como grafos, nos quais vértices representam palavras e arestas representam relacionamentos entre palavras; por exemplo, se um adjetivo modifica um substantivo, então o grafo deveria possuir uma aresta entre essas duas palavras. Devido à capacidade limitada da memória humana de curto prazo, Kornai e Tuza argumentam que este grafo deve ter lagruda de caminho limitada (mais especificamente, eles mencionam, largura de caminho no máximo igual a seis), caso contrário humanos não seriam hábeis a processar fala corretamente.

Algoritmos exponenciais

Muitos problemas em algoritmos de grafos podem ser solucionados eficientemente em grafos de baixa largura de caminho, usando programação dinâmica em uma decomposição em caminho de um grafo. Por exemplo, se uma ordenação linear dos vértices de um grafo G de n-vértices, com número de separação de vértices w, então é possível achar o conjunto máximo independente de G em tempo O(2^w n). Em grafos de largura de banda limitada, essa abordagem leva a algoritmos tratáveis a parâmetro fixo, parametrizados pela largura de caminho. Tais resultados não são frequentemente encontrados na literatura porque são interpretados por algoritmos similares parametrizados por largura de árvore; de qualquer maneira, largura de caminho torna-se notável em algoritmos de programação dinâmica baseados em largura de árvore na medição da complexidade de espaço destes algoritmos.

O mesmo método de programação dinâmica pode ser aplicado a grafos com largura de caminho limitada, levando a algoritmos que resolvem problemas de grafos não parametrizados em tempo exponencial. Por exemplo, combinando esta abordagem de programação dinâmica com o fato que grafos cúbicos terem largura de caminho n/6 + o(n) mostra que, em um grafo cúbico, o conjunto máximo independente pode ser construído em tempo O(2^n/6 + o(n)), mais rápido que métodos conhecidos anteriormente. Uma abordagem similar leva a algoritmos em tempo exponencial aperfeiçoados para os problemas de corte máximo e conjunto dominante em grafos cúbicos, e para diversos outros problemas de otimização NP-difíceis.

Veja também

• Boxidade, um meio diferente de medir a complexidade de um grafo arbitrário em termos de grafos intervalos
• Profundidade de árvore, um número que é limitado por uma família de grafo menor fechado se e somente se a família exclui um caminho
• Degeneração, uma medida de dispersão de um grafo que é no máximo igual à sua largura de caminho
• Largura de banda de grafos, um diferente problema NP-completo de otimização envolvendo layouts de grafos
• Número de Strahler, uma medida de complexidade de árvores ramificadas definidas similarmente à largura de caminho de árvores não ramificadas