Ideia principal da resposta: se reduzirmos uma instância do Conjunto Independente parametrizado para Vertex Cover parametrizada, o parâmetro com o qual terminamos depende do tamanho do gráfico e não depende apenas do parâmetro de entrada. Agora, para mais alguns detalhes.
Como você sabe, um problema parametrizado está no FPT (uniforme) se houver um algoritmo que decida se uma entrada ( x , k ) está contida em Q no tempo f ( k ) | x | O ( 1 ) para alguma função f .Q( x , k )Qf( K ) | x |O ( 1 )f
Como você pode decidir se um gráfico tem uma cobertura de vértice de tamanho k escolhendo uma aresta e ramificando em qual de seus dois pontos de extremidade colocar a cobertura de vértice, essa ramificação só vai k profunda (caso contrário, você colocou mais de k vértices na capa) e corre facilmente no tempo O ( 2 k n 2 ) ; portanto, a tampa k -Vertex está em FPT.GkkkO ( 2kn2)k
Agora suponha que queremos tentar usar esse algoritmo para mostrar que o Conjunto Independente parametrizado está no FPT; suponha que recebemos um gráfico em n vértices e desejamos decidir se ele possui um conjunto independente de tamanho ℓ . Isso equivale a perguntar se G tem uma cobertura de vértice de tamanho n - ℓ . Portanto, usamos o algoritmo acima para calcular a resposta em O ( 2 n - ℓ n 2 ) . Para o nosso algoritmo FPT, a função exponencial no tempo de execução pode depender do parâmetro, que é ℓ , mas NÃO pode depender do tamanho da entrada, que é nGnℓGn - ℓO ( 2n - ℓn2)ℓn; mas a abordagem que esboçamos usa o tempo exponencial em e, portanto, não é um parâmetro do FPT em relação ao parâmetro ℓ . É por isso que o fato de a tampa do vértice estar no FPT não implica que o conjunto independente esteja no FPT.n - ℓℓ
Eu não diria que a 'natureza' do problema muda, o que quer que isso signifique. Tudo o que muda é o parâmetro, ou seja, a maneira como você mede a dificuldade do problema.
Os gráficos com uma cobertura de vértices de tamanho no máximo são tão estruturados que é possível reduzi-los com eficiência: Podemos encontrar avidamente uma correspondência máxima de tamanho no máximo k, e o restante do gráfico é um conjunto independente de tamanho pelo menos n - 2 k . Usando regras de redução, como a redução da coroa, o número de vértices pode ser reduzido para no máximo 2 k .k k n - 2 k 2 k
Por outro lado, gráficos que possuem uma cobertura de vértices de tamanho no máximo (ou equivalente, o máximo de independentes independentes tem tamanho de pelo menos k ) não parece ter uma estrutura tão simples. Isso pode ser feito preciso, como você aponta: a estrutura deles nos permite codificar qualquer problema W [ 1 ] .n - k k W[ 1 ]
fonte
O seguinte pode dar alguma intuição para a diferença. Um subconjunto de vértices S é uma cobertura de vértice de G = (V, E) se e somente se VS for um conjunto independente, portanto, se MVC for o tamanho de uma cobertura de vértice mínima, MIS = | V | -MVC será o tamanho de o conjunto independente máximo. Um algoritmo FPT parametrizado por X permite um tempo de execução exponencial em função de X. Um gráfico aleatório em n vértices com probabilidade de borda metade tem com alta probabilidade MIS de tamanho cerca de 2logn e MVC de tamanho sobre n-2logn. Assim, pelo menos para esses gráficos, um algoritmo FPT parametrizado pelo MVC simplesmente permite muito mais tempo do que um parametrizado pelo MIS.
fonte
Embora eu concorde com o que os outros disseram, outra maneira que acho útil ao pensar sobre essas coisas é reformular o problema como um problema de reconhecimento, ou seja, "O gráfico de entrada pertence à família de gráficos com cobertura de vértices no máximo k?" / "O gráfico de entrada pertence à família de gráficos que possuem um conjunto independente de pelo menos k?".
Intuitivamente, uma família de gráficos mais restrita deve ser mais fácil de reconhecer do que uma família mais rica e mais geral. A família de gráficos de cobertura de vértices no máximo k é muito restrita; de fato, cada um desses gráficos pode ser descrito usando apenas bits, que é muito menor que o usual O ( n 2 )O ( k2+ 2kregistron ) O ( n2) bits necessários , assumindo que k é significativamente menor que n. Por outro lado, a família de gráficos de conjuntos independentes com pelo menos k é muito rica: qualquer gráfico pode ser editado para pertencer a ele removendo no máximo arestas.k2
Portanto, para mim, essa é uma explicação intuitiva do porquê eu esperaria que fosse mais fácil reconhecer uma pequena cobertura de vértice do que um pequeno conjunto independente. É claro que deveria ser óbvio que os pensamentos acima não estão nem perto de um argumento formal e acho que no final do dia a evidência mais convincente de que é realmente mais difícil reconhecer um conjunto independente de tamanho k é exatamente a dureza W de conjunto!
fonte
Essa é uma resposta muito indireta e pode não atender totalmente à sua preocupação. Mas o FPT e a hierarquia W estão intimamente ligados à aproximação (os problemas do FPT geralmente têm PTASs etc.). Nesse contexto, observe que, para qualquer gráfico, VC = n - MIS, portanto, uma aproximação para VC não fornece uma aproximação para MIS. É por isso que você precisa de reduções de L para aproximações. Suspeito que exista uma noção equivalente de "redução de preservação de kernel" para complexidade parametrizada também.
fonte