Problemas NP-difíceis em árvores

47

Vários problemas de otimização conhecidos por serem NP-hard em gráficos gerais são trivialmente solucionáveis ​​em tempo polinomial (alguns até em tempo linear) quando o gráfico de entrada é uma árvore. Os exemplos incluem cobertura mínima de vértices, conjunto independente máximo, isomorfismo do subgrafo. Cite alguns problemas de otimização natural que permanecem duros em NP nas árvores.

Shiva Kintali
fonte
1
Jukka, é discutível se "wiki da comunidade" for necessário aqui. Obviamente, problemas artificiais com pouca relevância provavelmente serão rebaixados, de qualquer maneira.
Ryan Williams
1
Eu também estou inclinado a pensar que CW não é necessário
Suresh Venkat
2
Não tenho certeza se CW é necessário. Não consigo pensar em nenhum problema em cima da minha cabeça. Parece que os pôsteres devem ser recompensados ​​por responder a essa pergunta.
Robin Kothari
5
Alguns hits aleatórios Google de trabalhos de pesquisa que mostram que um problema é NP-hard mesmo que a entrada é uma árvore: capacitada veículo roteamento , problema mínimo de latência , chamada programação ...
Jukka Suomela
4
Não foi isso que você pediu, mas vale a pena mencionar aqui: existem alguns problemas que são fáceis para as árvores, mas difíceis para a largura da árvore limitada. Por exemplo, caminhos separados por arestas (Nishizeki, Vygen, Zhou '01) e extensão da matriz de restrições (McDiarmid, Reed '03).
Diego de Estrada

Respostas:

23

Você pode encontrar exemplos "naturais" e "conhecidos" de problemas gráficos que são difíceis, mesmo que restritos a árvores, a partir de nossa referência padrão . Exemplos:

(Eles são formulados como problemas de árvore, mas você pode generalizá-los em gráficos arbitrários. Em seguida, as formulações acima são obtidas como o caso especial quando você restringe sua entrada a árvores.)


Uma receita mais geral para gerar problemas difíceis para as árvores: Pegue qualquer problema difícil de NP relacionado a superséries , supercordas , substrings , etc. Em seguida, re-interprete uma sequência como um gráfico de caminho rotulado. Em seguida, faça a pergunta análoga para gráficos gerais (subsequência ≈ gráfico menor, substring ≈ subgrafo). E sabemos que o problema é difícil de NP mesmo em árvores (e em caminhos).


Também existem muitos problemas que são difíceis para as estrelas ponderadas, pela redução do problema da soma de subconjuntos. Um exemplo natural é:

  • TSP com dois viajantes : dado um gráfico de borda e um limite , podemos encontrar dois passeios fechados e em modo que cada passeio tenha peso total no máximo e cada nó de seja coberto por pelo menos um caminhar?W C 1 C 2 L W LGWC1C2GWG

Novamente, é fácil criar variações do tema.

Jukka Suomela
fonte
Pena que o compêndio não é mais atualizado.
Anthony Labarre
O que é um "gráfico de caminho rotulado"?
david
29

É NP completo determinar se uma árvore pode ser incorporada à grade inteira bidimensional, com os vértices da árvore colocados em pontos distintos da grade e as arestas da árvore colocadas nas arestas da grade.

Ver, por exemplo, Gregori, IPL 1989 .

David Eppstein
fonte
Então, isso implica na dureza do desenho retilíneo das árvores? Existe um grau vinculado que preserva a dureza?
Mohammad Al-Turkistany
2
Quanto ao limite de grau: se existe um vértice de grau maior que quatro, nenhuma incorporação de grade é possível.
David Eppstein
Obrigado David, simples de declarar, mas um problema interessante.
Mohammad Al-Turkistany
Ah, a árvore de entrada também é uma árvore binária. Isso é ótimo!
Cyriac Antony
24

O problema do Group Steiner é um bom exemplo. A entrada para esse problema é um gráfico não ponderado com ponderação de arestas ek grupos de vértices . O objetivo é encontrar uma árvore de peso mínimo que contenha pelo menos um vértice de cada grupo. É fácil ver que o problema da tampa do conjunto é um caso especial, mesmo quando G é uma estrela. Portanto, é difícil aproximar o problema de um fator , a menos que P = NP. Além disso, foi demonstrado por Halperin e Krauthgamer que é difícil aproximar o problema de um fator para qualquer fixo, a menos que o NP tenha algoritmos de tempo quase polinomiais aleatórios ( veja o artigo para uma declaração precisa). Existe umS 1 , S 2 , , S k O ( log n ) O ( log 2 - ϵ n ) ϵ > 0 O ( log 2 n )G=(V,E)S1,S2,,SkO(logn)O(log2ϵn)ϵ>0O(log2n) aproximação das árvores por Garg, Konjevod e Ravi.

Chandra Chekuri
fonte
4
Aaah: o látex não formatado !! dói os olhos :)
Suresh Venkat
Bem, eu não sei como formatar o látex aqui :). Ponteiros ??
Chandra Chekuri 13/09/10
basta usar $ .. $ como de costume.
Suresh Venkat
ok tudo corrigido agora.
Suresh Venkat
22

Um dos problemas mais difíceis das árvores é o problema da largura de banda mínima. É -Hard em árvores de grau máximo 3. Também é NP-duro na lagarta circular de comprimento de cabelo 1.NP

Referências:

Michael R. Garey, Ronald L. Graham, David S.Johnson e Donald E. Knuth. Resultados de complexidade para minimização de largura de banda. SIAM J. Appl. Math., 34 (3): 477-495, 1978.

Burkhard Monien. O problema de minimização da largura de banda para lagartas com comprimento de cabelo 3 é NP-completo. SIAM J. Algebraic Discrete Methods, 7 (4): 505-512, 1986.

W. Unger. A complexidade da aproximação do problema da largura de banda. No FOCS, páginas 82–91, 1998

Mohammad Al-Turkistany
fonte
1
A versão corrigida do artigo de Unger são os resultados de Dureza para aproximar a largura de banda , Chandan Dubey, Uriel Feige e Walter Unger.
Yuval Filmus
14

O problema de multicutação de arestas não ponderadas é o seguinte: Dado um gráfico não direcionado , uma coleção de pares de vértices de e um número inteiro positivo , encontre se existe um subconjunto de no máximo arestas em cuja remoção desconecta todos os pares de vértices na coleção.G k S k GGGkSkG

Esse problema é difícil para NP (e MAX para SNP) em estrelas [ 1 ].

[ 1 ] Garg, Vazirani e Yannakakis, algoritmos de aproximação primal-dupla para fluxo integral e multicut em árvores , Algorithmica, 18 (1), pp 3-20, 1997.

gphilip
fonte
13

O problema dos bombeiros recebeu bastante atenção recentemente e é (surpreendentemente) difícil para NP em árvores de grau máximo 3 . Na verdade, é uma pergunta bastante natural, descrita da seguinte forma:

Um incêndio ocorre na raiz da árvore (ou mais geralmente, um vértice especificado em um gráfico). A cada passo, o bombeiro protege um vértice que não queima, após o que o fogo se espalha para todos os vizinhos desprotegidos. O processo termina quando não há vértice desprotegido próximo ao fogo. Existe uma estratégia para o bombeiro na qual no máximo vértices queimam?k

Ou uma variante, também NP-difícil : existe uma estratégia para o bombeiro na qual nenhuma folha queima?

Andrew D. King
fonte
8

Um problema que se pode pensar que NÃO seria difícil para as árvores, mas é, é o problema da etiqueta congelada na geometria computacional : brevemente, o problema de agendar ativações para robôs começando com um único bot acordado, em que makepan é a medida de custo.

Sabe-se que é NP-hard em gráficos de estrelas ponderadas. No entanto, está aberto se o problema é NP-difícil no avião. Pode-se argumentar que a dureza NP não vem da 'arborização', mas da 'métrica arbitrária', mas os gráficos em estrela fornecem apenas um espaço limitado de métricas.

Suresh Venkat
fonte
8

Dada uma árvore , uma partição de em níveis (isto é, arestas de conectam vértices dos níveis vizinhos e ), e um número inteiro . Você pode permutar os vértices dentro dos níveis, de modo que o número de cruzamento seja no máximo ?TV(T)kϕ:V(T){1,,k}Tii+1KK

Esse problema é NP-completo, comprovado por Martin Harrigan e Patrick Healy, Minimização de cruzamento de nível é NP-difícil para árvores , WALCOM 2011, LNCS 6552, pp. 70-76.k

user13136
fonte
8

A coloração Empire é NP-difícil para árvores.

Seja e números inteiros positivos fixos e seja um gráfico cujo conjunto de vértices é particionado em blocos (ou impérios), cada um contendo exatamente vértices. O -colouring problema - pede uma coloração dos vértices do grafo que usa no máximo cores, não atribui a mesma cor para vértices adjacentes em diferentes impérios e, inversamente, atribui a mesma cor a todos os vértices no mesmo império, desconsiderando as adjacências.rsGr(s,r)sCOLrGs

McGrae e Zito, Empires dificultam a cartografia: a complexidade do problema de coloração do império, LNCS 6986 (2011) 179–190, mostra que, para árvores,sCOLrs{3,,2r1}s

Jens G.
fonte
6

TSTT1TSTT1T

O problema é difícil de NP (na verdade, é difícil de aproximar) somente quando todas as árvores de entrada têm grau ilimitado.

Gianluca Della Vedova
fonte
6

Uma coloração harmoniosa de um gráfico simples é uma coloração de vértice adequada, de modo que cada par de cores apareça junto em no máximo uma aresta. O número cromático harmonioso de um gráfico é o menor número de cores em uma coloração harmoniosa do gráfico. Este problema de encontrar o Número Cromático Harmonioso mostrou-se NP-completo em árvores por Edwards e McDiarmid . De fato, eles também mostram que o problema permanece NP-completo para árvores de raio 3.

Ashutosh Rai
fonte
5

uu

Observe que no problema de TSP relacionado (e mais famoso), o objetivo é minimizar a latência máxima, e não a média. Eu acho que o TRP é geralmente considerado um problema mais complicado (na verdade, o TSP está em P para métricas de árvore).

A dureza de NP nas árvores foi mostrada no RA Sitters "O problema de latência mínima é NP-difícil para árvores ponderadas", ISCO 2002.

Michael Lampis
fonte
1
Esse é um bom problema!
Tayfun Pay
3

Há um problema (muito geral) que eu observei como parte de um projeto: uma variante desse problema permanece NP-difícil mesmo em gráficos com dois vértices e uma única aresta, e uma variante diferente é NP-difícil em árvores. Como a dureza NP da primeira variante obviamente não decorre da forma do gráfico, a segunda é provavelmente mais interessante.

SCG=(V,E)SVCVSC=sS|s|FfF|f|eEteRC×F(c,f)Rcf

sSAsfAs|f||s|PrGr=(c,f)RcsfAsD e r = ( c , f ) D e P r e Σ ( c , f ) D e | f | t eeDer=(c,f)DePre(c,f)De|f|te

Se você não precisa de todos os downloads a serem encaminhadas, mas em vez de tentar maximizar a soma dos filesizes dos downloads que são roteados que você pode facilmente reduzir subconjunto de soma para este problema: você tem um único servidor com grandes quantidades de espaço, um cliente único conectado ao servidor com uma borda com capacidade igual ao valor de destino da instância de soma do subconjunto e para cada número inteiro na instância de soma do subconjunto, você cria um arquivo com tamanho igual; o cliente então deseja baixar todos esses arquivos.

Uma variante (muito?) Mais interessante para essa pergunta é o caso de você tentar minimizar o número de arestas cuja capacidade é excedida - talvez a rede em que estamos trabalhando modele os cabos transatlânticos da Internet e substitua um cabo seja tão cara que a diferença no custo de atualização para um fator dois mais rápido e uma atualização para um fator três mais rápido é insignificante. Também dizemos que as veiculações de arquivos nos servidores já foram fornecidas e não podem ser modificadas; portanto, analisamos apenas os problemas de roteamento.

O problema da tampa do conjunto pode ser facilmente reduzido a essa variante. Estamos dado um conjunto chamado o universo e vários subgrupos deste universo. Somos solicitados a escolher a menor quantidade de subconjuntos, de modo que sua união seja igual ao universo. Para cada , criamos um arquivo de tamanho 1. Temos um único cliente que deseja baixar todos esses arquivos.S P ( U ) u UUSP(U)uU

Para cada subconjunto , criamos um 'cluster' de servidores: um cluster consiste em um único vértice (um roteador) conectado a vários servidores, de forma que os servidores estejam conectados apenas ao roteador. Para cada , adicionamos um único servidor ao cluster com o arquivo correspondente a . Esses clusters são então conectados ao cliente com uma borda de capacidade 1 (para que cada borda conecte o cliente ao roteador do cluster). Além disso, para cada cluster de servidor, adicionamos mais um servidor a esse cluster que hospeda um único arquivo novo (exclusivo para esse cluster) de tamanho 1. Todos esses arquivos (portanto, além dos arquivos correspondentes aos elementos do universo) são solicitados por o cliente.u s usSusu

A ideia é que o cliente precise dos arquivos exclusivos para todos os clusters de servidores, portanto, as bordas que conectam o cliente aos clusters de servidores já estão no limite de suas capacidades (suas capacidades são 1, os arquivos têm o tamanho 1). Se o cliente fizer o download de qualquer elemento do universo de qualquer cluster, a borda conectada a esse cluster ficará sobrecarregada. Como exigimos apenas minimizar o númerode sobrecargas (e não em quanto excedemos as capacidades), o cliente pode baixar o restante dos elementos do universo hospedado naquele cluster de servidores (para o restante dos elementos do subconjunto correspondente) sem penalidade. Portanto, isso corresponde ao subconjunto escolhido. O cliente deseja fazer o download de todos os arquivos do universo uma vez, para que o universo seja coberto e, para minimizar o número de arestas sobrecarregadas, precisamos minimizar o número de subconjuntos escolhidos.

Observe que a construção acima produz um gráfico em árvore, por isso é um exemplo de um problema de NP nas árvores.

Alex ten Brink
fonte
3

O Problema do Fluxo Incompleto. Na verdade, a UFP é difícil, mesmo em uma única borda (mochila).

Arindam Pal
fonte
3

G(V,E)NP

Formalmente, o problema é:

ISOMORFISMO GRÁFICO PARTICIONADO

T=(V,E)

{E1,E2}ET1=(V,E1)T2=(V,E2)

A coluna NP-completeness cita o manuscrito não publicado de Graham e Robinson, "Fatoração isomórfica IX: árvores pares".

DS Johnson, coluna NP-completeness: um guia contínuo, Journal of Algorithms 3 (1982), 288–300

Mohammad Al-Turkistany
fonte
2

De alguma forma, eu perdi o problema do número acromático na última resposta, mas esse é um dos problemas mais naturais que conheço, que são NP completos em árvores.

Uma coloração completa de um gráfico é uma coloração adequada, de modo que haja uma aresta entre cada par de classes de cores. A coloração pode ser declarada em contraste com a Coloração harmoniosa, como uma coloração adequada, de modo que cada par de cores apareça em pelo menos uma borda. Além disso, pode ser declarado como um homomorfismo completo (ou completo) para uma camarilha. O problema do número acromático é um problema de maximização , onde procuramos o maior número de classes de cores em uma coloração completa do gráfico.

Yannakakis e Gravil provaram que esse problema era difícil de usar no complemento dos gráficos bipartidos . Cairnie e Edwards ampliaram esse resultado e mostraram que o problema é NP-completo nas árvores .

Muito trabalho foi feito sobre esse problema no campo dos algoritmos de aproximação [ 3 , 4 , 5 ].

Ashutosh Rai
fonte
2

nknk

user1105
fonte
-1

O Circuit SAT nas árvores é NPC ?. Os vértices internos das árvores são rotulados como portas OR / AND. Folhas são entradas. Determine se existe um conjunto satisfatório de entradas para o circuito avaliar como True.

2k1

Chad Brewbaker
fonte
1
Umm, os circuitos que são árvores têm um nome: fórmulas. Naturalmente, a Formula SAT é NP-completa, já que 3-SAT ou mesmo CNF-SAT completo são seus casos especiais.
Emil Jeřábek apoia Monica
1
Como assim? Todas as fórmulas são árvores. Se você deseja restringir várias ocorrências de variáveis, isso é uma restrição adicional. (Também suponho que quando você escreve “inputs”, você realmente quer dizer “literais”, pois o circuito SAT com apenas AND, OR e literais positivos é um tempo trivialmente polinomial para começar.)
Emil Jeřábek apóia Monica
1
((a+b)+c)+d((a+b)+c)+a
1
(pq)p
1
Não é um problema de brinquedo. Esta é a terminologia padrão, quando quando dizemos que um circuito é uma árvore, isso não significa que as variáveis ​​apareçam apenas uma vez. De qualquer forma, e independentemente do que chamamos de problema, você propõe que é trivial como escrevi.
Kaveh