Problemas diretos de NP em DAGs

12

A largura da árvore mede o quão perto um gráfico está de uma árvore. Vários problemas difíceis de NP são tratáveis ​​em gráficos com largura de árvore delimitada. Se um problema persistir com NP em árvores, a largura da árvore não pode nos salvar. Essa foi a motivação por trás de uma das minhas perguntas anteriores, pedindo problemas difíceis de NP nas árvores.

Existem várias versões direcionadas da largura da árvore que medem a proximidade de um gráfico direcionado a um gráfico acíclico direcionado (DAG). Quais são alguns problemas direcionados que permanecem difíceis de usar NP nos DAGs? Um problema direcionado faz uso essencial das direções das arestas. Por exemplo, o caminho hamiltoniano é um problema direcionado, enquanto a cobertura de vértices não é. Uma das respostas à minha pergunta anterior deu uma receita geral para gerar problemas difíceis para as árvores. Existe tal receita para DAGs?

np-hardness directed-acyclic-graph Shiva Kintali
fonte

Respostas:

7

Isso visa apenas responder parcialmente à primeira pergunta do post:

Quais são alguns problemas direcionados que permanecem difíceis de usar NP nos DAGs?

Em [1], são apresentados alguns problemas naturais em gráficos direcionados que permanecem difíceis de usar NP em DAGs. A motivação do artigo é encontrar uma "boa" medida semelhante à largura da árvore para os dígrafos. Eles argumentam que a desvantagem de muitas medidas para os dígrafos é que eles são constantes para os DAGs, mas muitas contrapartes direcionadas de problemas naturais permanecem duras para os DAGs. Para mais informações sobre esse tópico, consulte também [2] e as referências desses documentos.

[1] Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith: Sobre medidas de largura de dígrafos em algoritmos parametrizados. IWPEC 2009: 185-197. Versão completa

[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith e Somnath Sikdar: existem boas medidas de largura do dígrafo ?. IPEC 2010, para aparecer. arXiv

Serge Gaspers
fonte
6

Sabe-se que vários problemas de roteamento são difíceis de NP e até difíceis de se aproximar de fatores polinomiais em DAGs. Isso inclui problemas como caminhos máximos de desconexão de borda e minimização de congestionamento. Veja os artigos de Andrews, Chuzhoy, Khanna, Zhang e outros para mais dicas.

Chandra Chekuri
fonte
1

φ:=∃C1C2C3[∀x(C1x∨C2x∨C3x)∧⋀i=1,2,3∀x,y(¬Cix∨¬Ciy∨¬E(x,y))]GG′E(x,y)φE(x,y)∨E(y,x)G⊨φ⟺G′⊨φ′

Regularidade
fonte
Parece que esse problema não está usando as instruções das bordas. Estou procurando problemas direcionados.
Shiva Kintali 5/10/10
@Shiva: Por que isso não atende aos seus critérios para um problema direcionado?
András Salamon
@ András: A coloração do gráfico se preocupa com a presença de uma aresta (u, v). Não importa se a aresta é direcionada de u para v ou de v para u. Por outro lado, o Caminho Hamiltoniano usa as direções das arestas. É possível alterar as direções de algumas arestas e converter uma instância YES em uma instância NO.
Shiva Kintali 5/10/10
@Shiva: Então você quer uma propriedade que seja expressa por uma fórmula que não seja simétrica (invariável sob permutação de variáveis)?
András Salamon
@ András: Exatamente.
Shiva Kintali 06/10/10
1

O famoso problema OPEN [8] da lista de Garey e Johnson está além de P, mas pode ser provado ser NP-C. Esse problema está no DAG. A cada rodada, você pode excluir no máximo três vértices que não têm aresta de entrada. Decida se todos os vértices do DAG podem ser excluídos em K rodadas? ABERTO desde 1970.

Peng Zhang
fonte