Problemas que são NP mas polinomiais em gráficos de largura de árvore limitada

7

Eu ouvi aqui que o problema ciclo hamiltoniano é polinomial em gráficos de treewidth limitada.

Estou interessado em exemplos / referências a diferentes problemas que são essencialmente difíceis, mas que possuem complexidade polinomial em gráficos de largura de árvore limitada.

seteropere
fonte

Respostas:

8

Provavelmente existem milhares de exemplos; há uma pequena lista no ISGCI ; o artigo da Wikipedia tem muitos links. Pesquise "largura da árvore limitada" e "largura da árvore com complexidade parametrizada" para muitos, muitos mais.

Essencialmente, os problemas se tornam fáceis em gráficos de largura de árvore limitada, porque:

  1. Embora seja NP-completo para determinar se um gráfico tem largura de árvore no máximo k [1], existe, para cada k um algoritmo de tempo linear para calcular uma decomposição em árvore de qualquer gráfico que realmente tenha largura de árvore k [2]

  2. Depois de decompor a árvore, você pode resolver muitos problemas através da programação dinâmica.

Um exemplo simples, que nem usa programação dinâmica, é o problema do Clique. Qualquer clique de um gráfico deve estar completamente contido em algum nó da decomposição da árvore. Isso significa que um gráfico de largura de árvore k não pode ter nenhum grupo de tamanho maior que k+1 1 e, para encontrar um grupo de tamanho no máximo k+1 1, basta ver se cada nó da decomposição contém a clique que você está procurando. Isso pode ser feito em tempo linear se k é uma constante fixa, já que você está apenas procurando cliques em O(n) gráficos que cada um tem no máximo k+1 1 vértices.

Para um exemplo mais complicado, suponha que você queira saber se um gráfico Gda largura da árvore 4 é de 3 cores. Primeiro, calcule a decomposição da árvore. Cada vértice da árvore corresponde a um subgrafo de no máximo 5 vértices de G. Para cada folha da árvore, calcule por força bruta todas as três cores dos subgráficos correspondentes. Isso ocorre no tempo polinomial, porque existem no máximo n folhas, cada uma corresponde a um subgrafo com no máximo 5 vértices e existem no máximo 35=2433 cores de qualquer subgrafo. Agora, para cada vértice v da árvore adjacente a uma folha, enumere todas as três cores compatíveis com as possíveis cores das folhas adjacentes a v. (Ou seja, as três cores do subgrafo correspondentes a v que pode ser estendido a uma coloração 3 do gráfico correspondente a ve todas as folhas adjacentes.) Nesse ponto, você pode esquecer as cores das folhas, pois tudo o que você precisa saber sobre elas agora está codificado nos vértices da distância-1. Agora, itere a árvore. Você pode imaginar fazendo algo semelhante ao caminho hamiltoniano, construindo um caminho através de toda a árvore juntando caminhos nas subárvores; isso é mais complicado.


[1] Arnborg, Corneil e Proskurowski, "Complexidade de encontrar embeddings em uma árvore k"., SIAM Journal on Matrix Analysis and Applications 8 (2): 277-284, 1987. DOI .

[2] Bodlaender, "Um algoritmo de tempo linear para encontrar decomposições de árvores de pequena largura de árvore", SIAM Journal on Computing 25 (6): 1305–1317, 1996. DOI .

David Richerby
fonte
essa largura de árvore limitada é uma suposição, certo? Quero dizer que não é exist propriedade nestes problemas
seteropere
Não sei bem o que você quer dizer. Por todos esses problemas e por todosk, existe um algoritmo polytime que resolve o problema em todos os gráficos de largura de árvore, no máximo k, mas falha nos gráficos de largura de árvore k+1 1ou melhor. Todos esses problemas têm instâncias "yes" de todas as larguras de árvores. Por exemplo, existem gráficos hamiltonianos de todas as larguras de árvores maiores que 1 e até mesmo gráficos de 2 cores de todas as possíveis larguras de árvores (por exemplo, grades).
David Richerby
Perdoe minha ignorância, David, mas como estabelecemos o valor para k?
Seteropere
11
@seteropere A afirmação é verdadeira para todos os valores de k. Portanto, por exemplo, se você achar que todos os gráficos com os quais você precisa trabalhar possuem uma largura de árvore entre 1 e 5, use o algoritmo parak=5.
David Richerby
5

Normalmente, para muitos "problemas locais", como VertexCover ou EundependentSet (o que significa que uma solução pode ser verificada verificando a vizinhança de cada vértice), os métodos de programação dinâmica padrão são executados em ctw|V|O(1 1) hora, onde tw é a largura da árvore do gráfico de entrada e cé alguma constante (pequena). Para muitos desses problemas, temos limites superior e inferior correspondentes para o tempo de execução da solução ideal, assumindo a chamada hipótese de tempo exponencial forte (SETH).

Em certo sentido, problemas com alguma "restrição global" (como conectividade) parecem mais difíceis. Para tais problemas, o algoritmo DP típico deve considerar todas as maneiras pelas quais a solução pode atravessar o separador correspondente da decomposição da árvore, ou seja,Ω(ss), Onde sé o tamanho do separador. Para mais, você pode consultar o artigo da FOCS'11 de Cygan et al., Versão arXiv aqui . Eles consideram os algoritmos de Monte Carlo para problemas com restrições globais. Há trabalhos subseqüentes nessa direção que investiga a "necessidade" de aleatoriedade.

Você também pode dar uma olhada no Capítulo 5 de Fomin, Fedor V. e Dieter Kratsch. Algoritmos exponenciais exatos. Springer, 2010.

Juho
fonte
4

Talvez você possa começar com:

H. Bodlaender e A. Koster, otimização combinatória em gráficos de largura de árvore limitada, The Computer Journal 51 (3), 255-269, 2008.

Encontrei essa referência em "Recursos" a partir daqui .

fidbc
fonte
1

Aqui está um estudo recente desse fenômeno de largura da árvore, limitando a complexidade do problema e movendo-o para P do ponto de vista da instância do SAT (dureza). Isso pode estar subjacente a uma estrutura maior para ajudar a entender a simplificação entre outros problemas completos do NP (por meio de reduções no SAT).

Backdoors fortes para a largura da árvore limitada SAT Gaspers / Szeider 2012

A decomposição pode ser considerada em termos da largura de árvore de um gráfico que está associada à fórmula CNF fornecida, por exemplo, considerando cláusulas e variáveis ​​como vértices do gráfico e tornando uma variável adjacente a todas as cláusulas em que aparece. Por outro lado, um forte conjunto backdoor de uma fórmula CNF é um conjunto de variáveis, de modo que cada atribuição parcial possível a esse conjunto mova a fórmula para uma classe fixa para a qual (#) SAT pode ser resolvido em tempo polinomial. Neste artigo, combinamos as duas abordagens acima. Em particular, estudamos a questão algorítmica de encontrar um pequeno backdoor forte definido na classe W_t de fórmulas CNF cujos gráficos associados tenham largura de árvore no máximo t.

vzn
fonte