O que separa problemas globais fáceis de problemas globais difíceis em gráficos de largura de árvore limitada?

Muitos problemas de gráfico rígido são solucionáveis ​​em tempo polinomial em gráficos de largura de árvore limitada . De fato, os livros didáticos geralmente usam, por exemplo, conjunto independente como exemplo, o que é um problema local . Grosso modo, um problema local é um problema cuja solução pode ser verificada examinando uma pequena vizinhança de cada vértice.

Curiosamente, mesmo problemas (como o caminho hamiltoniano) de natureza global ainda podem ser resolvidos com eficiência para gráficos de largura de árvore limitada. Para tais problemas, os algoritmos de programação dinâmica usuais devem acompanhar todas as maneiras pelas quais a solução pode atravessar o separador correspondente da decomposição da árvore (consulte, por exemplo, [1]). Algoritmos randomizados (baseados no chamado cut'n'count) foram dados em [1], e algoritmos aprimorados (mesmo determinísticos) foram desenvolvidos em [2].

Não sei se é justo dizer que muitos, mas pelo menos alguns problemas globais podem ser resolvidos com eficiência em gráficos de largura de árvore limitada. E quanto aos problemas que permanecem difíceis nesses gráficos? Suponho que eles também sejam de natureza global, mas o que mais? O que separa esses problemas globais difíceis dos problemas globais que podem ser resolvidos com eficiência? Por exemplo, como e por que métodos conhecidos falhariam em fornecer algoritmos eficientes para eles?

Por exemplo, pode-se considerar o (s) seguinte (s) problema (s):

Borda extensão precoloring Dado um grafo com algumas bordas coloridas, decidir se esta coloração pode ser estendido para uma adequada k -Edge-coloração do grafo G .$G$$k$$G$

A extensão de pré-coloração da borda (e sua variante de coloração da borda da lista) é NP-completa para gráficos paralelos em série bipartidos [3] (esses gráficos têm largura de árvore no máximo 2).

Coloração mínima da aresta da soma Dado um gráfico , encontre uma coloração da aresta χ : E → N tal que se e 1 e e 2 tiverem um vértice comum, então χ ( e 1 ) ≠ χ ( e 2 ) . O objetivo é minimizar E ′ χ ( E ) = ∑ e ∈ E χ ( e ) , a soma da coloração.$G=(V,E)$$\chi : E \to \mathbb{N}$$e_1$$e_2$$\chi(e_1) \neq \chi(e_2)$$E'_\chi(E) = \sum_{e \in E} \chi(e)$

Em outras palavras, precisamos atribuir números inteiros positivos às arestas de um gráfico, de modo que as arestas adjacentes recebam números inteiros diferentes e a soma dos números atribuídos seja mínima. Esse problema é difícil de NP para 2 árvores parciais [4] (ou seja, gráficos de largura de árvore no máximo 2).

Outros problemas difíceis incluem o problema de caminhos disjuntos de borda, o problema de isomorfismo do subgrafo e o problema de largura de banda (veja, por exemplo, [5] e suas referências). Para problemas que permanecem difíceis, mesmo em árvores, consulte esta pergunta .

[1] Cygan, M., Nederlof, J., Pilipczuk, M., van Rooij, JM e Wojtaszczyk, JO (2011, outubro). Resolução de problemas de conectividade parametrizados por largura de árvore em tempo exponencial único. In Foundations of Computer Science (FOCS), 2011 IEEE 52º Simpósio Anual em (pp. 150-159). IEEE.

[2] Bodlaender, HL, Cygan, M., Kratsch, S. e Nederlof, J. (2013). Algoritmos de tempo exponencial determinístico único para problemas de conectividade parametrizados por largura de árvore. Em Autômatos, Idiomas e Programação (pp. 196-207). Springer Berlin Heidelberg.

[3] Marx, D. (2005). NP - completude da extensão da lista de cores e pré-cores nas bordas dos gráficos planares. Journal of Graph Theory, 49 (4), 313-324.

[4] Marx, D. (2009). Resultados de complexidade para coloração mínima da aresta da soma. Matemática Aplicada Discreta, 157 (5), 1034-1045.

[5] Nishizeki, T., Vygen, J., & Zhou, X. (2001). O problema dos caminhos disjuntos da borda é NP-completo para gráficos paralelos em série. Matemática Aplicada Discreta, 115 (1), 177-186.

A maioria dos algoritmos para gráficos de largura de árvore limitada é baseada em alguma forma de programação dinâmica. Para que esses algoritmos sejam eficientes, precisamos vincular o número de estados na tabela de programação dinâmica: se você deseja um algoritmo de tempo polinomial, precisa de um número polinomial de estados (por exemplo, n ^ tw), se desejar mostre que o problema é FPT, você geralmente deseja mostrar que o número de estados é uma função da largura da árvore. O número de estados normalmente corresponde ao número de diferentes tipos de soluções parciais ao quebrar o gráfico em algum pequeno separador. Assim, é fácil um problema nos gráficos de largura da árvore limitada, geralmente porque as soluções parciais que interagem com o mundo externo através de um número limitado de vértices têm apenas um número limitado de tipos. Por exemplo, no problema do conjunto independente, o tipo de solução parcial depende apenas de quais vértices de limite são selecionados. No problema do ciclo hamiltoniano, o tipo de solução parcial é descrito pela maneira como os subcaminhos da solução parcial correspondem aos vértices do limite entre si. Variantes do teorema de Courcelle fornecem condições suficientes para um problema ter a propriedade de que soluções parciais têm apenas um número limitado de tipos.

Se um problema é difícil nos gráficos de largura da árvore delimitada, geralmente é devido a um dos três motivos a seguir.

1. Existem interações no problema não capturadas pelo gráfico. Por exemplo, Steiner Forest é NP-hard em gráficos de largura de árvore 3, intuitivamente, porque os pares de origem e destino criam interações entre vértices não adjacentes.

Elisabeth Gassner: O problema da floresta de Steiner revisitado. J. Algoritmos Discretos 8 (2): 154-163 (2010)

MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Dániel Marx: esquemas de aproximação para a floresta Steiner em gráficos planares e gráficos de largura de árvore limitada. J. ACM 58 (5): 21 (2011)

2. O problema é definido nas bordas do gráfico. Então, mesmo que uma parte do gráfico seja anexada ao restante do gráfico por meio de um número limitado de vértices, pode haver muitas arestas incidentes nesses poucos vértices e, em seguida, o estado de uma solução parcial pode ser descrito apenas descrevendo o estado de todas essas arestas. Foi isso que tornou os problemas difíceis [3,4].

3. Cada vértice pode ter um grande número de estados diferentes. Por exemplo, a Capa de vértice capacitado é W [1] - parametrizada por largura de árvore, intuitivamente, porque a descrição de uma solução parcial envolve não apenas declarar quais vértices do separador foram selecionados, mas também quantas vezes cada vértice selecionado do separador foi usado para cobrir bordas.

Michael Dom, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger: Dominação Capacitada e Cobertura: Uma Perspectiva Parametrizada. IWPEC 2008: 78-90

Minha sugestão seria examinar atentamente o teorema de Courcelle , de que problemas expressáveis ​​em (certas extensões da) lógica monádica de segunda ordem têm algoritmos FPT quando parametrizados pela largura da árvore. Minha suspeita é que isso cubra muitos ou a maioria dos exemplos conhecidos de problemas de FPT para esses gráficos. Nessa visão, sua distinção local / global parece estar intimamente relacionada à distinção entre problemas expressáveis ​​em MSO existencial versus problemas que têm níveis mais altos de quantificação em suas formulações de MSO. Para retornar à sua pergunta real, a falta de uma formulação MSO (que pode ser comprovada incondicionalmente em muitos casos usando idéias relacionadas ao teorema de Myhill-Nerode ) seria evidência da falta de um algoritmo FPT (mais difícil de provar sem suposições teóricas de complexidade).

Eu acho que um desses exemplos é o problema de corte mais escasso. O problema de corte mais esparso uniforme é solucionável em gráficos de largura de árvore delimitada, mas o problema de corte mais esparso ponderado não é sequer aproximado (melhor que 17/16) em gráficos de largura de árvore limitada.

Existem muitas variantes diferentes do problema de corte mais escasso, mas uma das mais conhecidas é a seguinte.

$G=(V,E)$$w:E(G)\rightarrow N$$E(S,V\setminus S) \subseteq E(G)$$S \subset V$$\frac{W(E(S,V\setminus S))}{|S||V\setminus S|}$$E'\subseteq E(G)$$W(E')=\sum_{e\in E'}w(e)$

O ingrediente principal é feito de duas coisas:

1. Funções adicionais, como aqui a função de peso. Mas ainda existem alguns problemas com a função de ponderação que não são muito difíceis em gráficos não direcionados de largura de árvore delimitada.

2. A natureza do problema de corte mais escasso. Realmente existe mais de uma dependência para programação dinâmica na definição do problema. Intuitivamente, a boa solução é a que dividimos um gráfico (removendo algumas arestas) em dois tamanhos quase iguais; por outro lado, nessa partição, excluímos o menor número de arestas que usamos. A razão pela qual o problema é difícil no gráfico de largura de árvore limitada é que devemos aplicar a programação dinâmica em duas direções, mas ambas as direções dependem uma da outra.

Em geral, se o problema é de tal forma que precisa de mais de uma dimensão para programação dinâmica e também essas dimensões dependem uma da outra, então o problema pode ser difícil em gráficos de largura de árvore delimitada. Podemos ver esse padrão nos dois problemas da pergunta e no problema de corte mais esparso. (No primeiro problema, queremos manter a coloração anterior, por outro lado, mantenha a coloração o mais pequena possível, no segundo problema, obviamente, existem duas funções que dependem uma da outra)