Largura de caminho
De Wikipedia, a enciclopédia encyclopedia
Em teoria dos grafos, uma decomposição em caminho de um grafo G é, informalmente, uma representação de G como um caminho "alargado",[1] 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,[2] 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.[3]
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,[2] e os "vórtices" aparecendo na teoria geral de estrutura para famílias fechadas sob menores de grafos tem caminhos de largura delimitados.[4] 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.[5][6] 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.[7] 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.[8][9] 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.[10] 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.[11]