Implicações de um problema no XP quando parametrizado por diâmetro

8

Seja um problema gráfico completo de NP. Suponha que X seja solucionável em tempo polinomial em gráficos de diâmetro delimitado. Em outras palavras, X parametrizado por diâmetro está no XP. (Lembre-se de que um problema está no XP se ele puder ser resolvido no tempo n f ( k ) ). Isso implica solvabilidade no tempo de XP para outros parâmetros interessantes?XXXnf(k)

Em caso afirmativo, existe talvez uma lista ou rede mais ou menos "padrão" de parâmetros e como eles se relacionam documentados em algum lugar?

graph-theory parameterized-complexity fixed-parameter-tractable Juho
fonte

Respostas:

10

Eu acho que a Figura 1 (página 4) do artigo " Novas raças em algoritmos parametrizados " de Komusiewicz e Niedermeier é o que você está procurando.

Em particular, estar em XP para o diâmetro do parâmetro implica estar em XP para os parâmetros: conjunto dominante mínimo, conjunto independente máximo, cobertura mínima de clique, distância à cografia, distância ao co-cluster, distância ao clique, distância ao cluster, cobertura de vértice, e edição de cluster.

Edouard Bonnet
fonte
Ótimo, obrigado! Tive a sensação de ter visto uma figura assim antes, mas não consegui localizá-la. Pode-se notar que "grau médio" pode ser adicionado à figura e conectado a uma linha de "degeneração".
Juho 22/03
1

Recentemente, o ISGCI adicionou parâmetros. Eles ainda estão na versão beta no momento da redação, mas pode-se observar o diâmetro : o conjunto dominante mínimo é um limite superior mínimo e, seguindo a trilha para cima, encontramos o conjunto independente máximo e assim por diante.

Eles fazem referência, por exemplo, ao manuscrito de 2013 de Sorge e Weller, disponível aqui (veja a Figura 1).

Juho
fonte