Algoritmos exatos para o conjunto de dominação r em gráficos de largura de árvore limitada

14

Dado um gráfico, , que deseja encontrar uma óptima -domination para . Isto é, I quer um subconjunto de de tal modo que todos os vértices em estão a uma distância de, no máximo, de algum vértice em , enquanto minimiza o tamanho de .G=(V,E)rGSVGrSS

Pelo que verifiquei até agora, obtive o seguinte: Existe um problema relacionado à localização de um centro em um gráfico que é um subconjunto de tamanho no máximo modo que todos os vértices no gráfico são a uma distância de atmost de algum vértice em (aqui ambos e são partes da entrada) para os quais Demaine et al . tenha um algoritmo FPT para gráficos planares. Caso contrário, o problema é -hard para .(k,r)SkrS|S|krW[2]r=1

Sabe-se algo sobre a complexidade exata do problema de domínio- para gráficos de largura de árvores delimitadas ou mesmo apenas para árvores? (O MS-domínio de é definível? O problema usual do conjunto de domínio é o MSO - o que permitiria usar o teorema de Courcelle para concluir que existe um algoritmo de tempo linear para o problema). Existem resultados de dureza condicional conhecidos sobre esse problema?rrk

Nikhil
fonte
5
Uma óptima -domination para é um domínio óptimo para o th poder e vice-versa. Portanto, o problema de domínio é solucionável em tempo polinomial para árvores e, mais geral, para gráficos de largura de árvore limitada. rGrGrr
vb le
3
@ vble Eu acho que é fixo. Mas por que o problema de dominação é solucionável em gráficos de largura de árvores delimitadas? o poder de tais gráficos tem largura de árvore ilimitada. rr
Peng S
6
Sim, é fixo, obrigado. Sim, possui largura de árvore ilimitada, mas largura de clique limitada (devido a Gurski e Wanke) e o problema de dominação usual é definível pelo MSO. rGr
vb le
Obrigado @vble! Você pode fornecer referências e fazer do seu comentário uma resposta?
Nikhil
@ Nikhil: feito.
vb le

Respostas:

15

Uma dominação (ideal) para G é uma dominação (ideal) para a r- ésima potência G r e vice-versa ( G r é obtido de G adicionando novas arestas entre vértices distintos de distância no máximo r ).rGrGrGrGr

Os seguintes fatos são bem conhecidos: (1) Todos os poderes de um gráfico fortemente cordal são fortemente cordais (A. Lubiw, tese de mestrado; ver também Dahlhaus & Duchet, Em gráficos fortemente cordais, Ars Combin. 24 B (1987) 23-30 ) e (2) A dominação é solucionável em tempo linear para gráficos fortemente cordais (M. Farber. Dominação, dominação independente e dualidade em gráficos fortemente cordais, Discrete Appl. Math., 7 (1984) 115-130). Portanto, a dominação é solucionável em tempo polinomial para gráficos fortemente cordais, em particular para árvores ( r fixas ou não).rr

Gurski & Wanke provou no presente documento que a facção-largura de é, no máximo, 2 ( r + 1 ) tw ( L ) + 1 - 2 , onde tw ( L ) é a árvore de largura de L . Assim, para r fixo , os résésimos potentes dos gráficos de largura de árvore limitada têm largura de clique limitada. Portanto, para r fixo , a dominação r é passível de solução em tempo polinomial para gráficos de largura de árvore limitada (pelo teorema de Courcelle). Gr2(r+1)tw(G)+1-2tw(G)Grrrr

vb le
fonte
9

É muito fácil fazer programação dinâmica em gráficos de largura de árvore para esse problema. Pode-se manter para cada vértice em uma bolsa a menor distância até algum vértice na solução parcial e a distância para a solução futura necessária para dominar os vértices não denominados.k

No total, isso fornece um tamanho de tabela de portanto, para r fixo, esse problema é parametrizado em FPT por largura de árvore; no entanto, se r não for corrigido, isso se tornará um algoritmo XP. Tanto quanto sei, a questão de saber se esse problema é FPT para todos os valores de r está aberta.O(rk)rrr

Martin Vatshelle
fonte
Talvez mude para r O ( k ) ? rkrO(k)
Daniello
9

Dawar e Kreutzer mostraram que o problema é tratável por parâmetros fixos em classes densas de gráficos em nenhum lugar, o que inclui os gráficos planares, os gráficos da largura da árvore delimitada (local) e todas as classes com menores excluídos (localmente).

Dvorak mostrou que existe uma aproximação polinomial do fator constante de tempo para classes de expansão limitada, que inclui gráficos planares, gráficos de largura de árvore limitada e todas as classes com menores excluídos.

Sebastian Siebertz
fonte
5

Há um artigo recente de Glencora Borradaile, Hung Le: Programa Dinâmico Ideal para Problemas de Dominação r sobre Decomposições de Árvores (IPEC 2016). Aqui eles mostram que existe um algoritmo que, dado como entrada um gráfico , um número inteiro r , e uma decomposição em árvore de G de largura w , calcula um conjunto ótimo de domínio R de G no tempo O ( ( 2 r + 1 ) w n ) . Além disso, eles mostram que é o melhor que se pode fazer, no seguinte sentido: um algoritmo com tempo de execução O ( ( 2GrGwrGO((2r+1)wn) para ε > 0 em contradição com a forte exponencial Tempo hipótese.O((2r+1ϵ)wnO(1))ϵ>0

daniello
fonte
2

Um algoritmo seqüencial linear para calcular uma dominação r ideal para uma árvore é devido a Slater:

P. Slater. Dominação R em gráficos. J. ACM, 23 (3): 446–450, julho de 1976. doi: 10.1145 / 321958.321964

Um algoritmo distribuído para a mesma configuração é devido a Turau e Köhler:

Volker Turau e Sven Köhler. Algoritmo Distribuído para Domínio Mínimo de Distância-k em Árvores. Journal of Graph Algorithms and Applications, 19 (1): 223-242,5 (consulte http://jgaa.info/getPaper?id=354 )

Volker Turau
fonte