Complexidade parametrizada do número de interseção do gráfico

17

E se alguma coisa for conhecida sobre a complexidade parametrizada da computação do número de interseção de um gráfico (o menor número de cliques necessário para cobrir todas as suas arestas)?

Há muito que se sabe que o NP está completo, e obviamente é o FPT porque possui um núcleo: se você pode cobrir um gráfico com panelistas, existem no máximo 2 k vizinhanças fechadas diferentes de vértices (dois vértices têm as mesmas vizinhanças se eles pertencem ao mesmo conjunto de panelinhas) e você pode manter apenas um vértice por bairro. Essa observação está na literatura em algum lugar? Que tipo de dependência de k é conhecida?k2kk

David Eppstein
fonte

Respostas:

17

O problema foi estudado sob o nome Edge Clique Cover, e as observações feitas sobre a redução de dados foram usadas para obter um kernel com 2 ^ k vértices. É um problema aberto de longa data se existe um kernel polinomial. Eu não sei sobre bons limites no tempo de execução, consulte http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf

Bart Jansen
fonte
4
Evidentemente um kernel polinomial é inviável, de acordo com alguns desenvolvimentos bastante recentes: arxiv.org/abs/1111.0570
Neeldhara