Complexidade parametrizada do Hitting Set na dimensão VC finita

37

Estou interessado na complexidade parametrizada do que chamarei de problema do conjunto de batida d-dimensional: dado um espaço de intervalo (isto é, um sistema definido / hipergrafo) S = (X, R) tendo a dimensão VC no máximo d e um número inteiro positivo k, X contém um subconjunto de tamanho k que atinge todos os intervalos em R? A versão parametrizada do problema é parametrizada por k.

Para quais valores de d é o problema do conjunto de batidas d-Dimensional

  • no FPT?
  • em W [1]?
  • W-1-difícil?
  • W [2] -hard?

O que eu sei pode ser resumido da seguinte forma:

  • O conjunto de batidas unidimensionais está em P e, portanto, em FPT. Se S tem a dimensão 1, não é difícil mostrar que existe um conjunto de tamanho 2 ou a matriz de incidência de S é totalmente equilibrada. Em ambos os casos, podemos encontrar um conjunto mínimo de batidas no tempo polinomial.

  • O conjunto de batidas em 4 dimensões é W [1] -hard. Dom, Fellows e Rosamond [PDF] provaram a dureza W [1] para o problema de esfaquear retângulos paralelos ao eixo em R ^ 2 com linhas paralelas ao eixo. Isso pode ser formulado como conjunto de batidas em um espaço de intervalo da dimensão 4 do VC.

  • Se nenhuma restrição for colocada em d, teremos o problema padrão do Conjunto de Acertos, que é W [2] -complete e NP-complete.

  • Langerman e Morin [citeseer link] fornecem algoritmos FPT para Set Cover em dimensão restrita, embora seu modelo de dimensionalidade limitada não seja o mesmo que o modelo definido pela dimensão VC limitada. Seu modelo não parece incluir, por exemplo, o problema de acertar meios espaços com pontos, embora o problema do protótipo para seu modelo seja equivalente a atingir hiperplanos com pontos.

James King
fonte
4
Ótima pergunta!
András Salamon

Respostas:

14

Eu acho que esse problema é muito difícil. Não sabemos a resposta para problemas muito mais fáceis nesta família. Por exemplo, dado um conjunto de n pontos no plano e um conjunto de (digamos n) discos de unidade, decida se existe uma cobertura dos pontos por k dos discos de unidade. Existe um algoritmo de tempo n ^ O (k) fácil para isso, e eu não ficaria surpreso se, usando idéias conhecidas, é possível fazer n ^ O (sqrt {k}) (mas mesmo isso não é óbvio), mas fazendo f ( k) * n ^ {O (1)} está aberto e, de fato, seria bastante interessante. Uma aproximação (1 + eps) segue o trabalho de Mustafa e Ray http://portal.acm.org/citation.cfm?id=1542362.1542367 .

BTW, para a versão contínua em que qualquer disco de unidade é permitido, é possível resolver o problema em n ^ {O (k)} tempo. Um PTAS neste caso também é bastante fácil usando grades deslocadas.

Sariel Har-Peled
fonte
4

Abordamos esta questão em uma nova pré-impressão: http://arxiv.org/abs/1512.00481

Hitting Set em hipergrafos de baixa dimensão VC (Karl Bringmann, László Kozma, Shay Moran, NS Narayanaswamy).

Acontece que Hitting Set já é W [1] quando a dimensão VC é igual a 2.

László Kozma
fonte