W [1] - problemas difíceis com algoritmos de aproximação de tempo do FPT

9

Estou procurando problemas difíceis de resolver no tempo do FPT, mas que possuem um algoritmo de aproximação. Ou seja, problemas que são:

R1. W [1] -hard.

R2. Admita um algoritmo de aproximação (de preferência constante) no tempo do FPT.

O problema com o qual estou familiarizado é contar o número de caminhos simples de comprimento em um gráfico. É conhecido por ser #W [1] -hard , mas admite uma aproximação no tempo do FPT (para qualquer constante ).( 1 + ϵ ) ϵk(1+ϵ)ϵ

Também interessantes seriam os problemas que satisfazem R1 e R2 e também:

R3. Existe tal que o problema não é aproximado no tempo do FPT (a menos que W [1] = FPT).( 1 + ϵ )ϵ>0 (1+ϵ)

Que outros problemas satisfazem R1 e R2, e possivelmente R3?

RB
fonte

Respostas:

9

No problema Transversal do Ciclo Estranho Dirigido, a entrada é um gráfico e a tarefa é encontrar um conjunto menor de vértices de modo que não tenha ciclos (direcionados) de comprimento ímpar. Na versão parametrizada, também recebemos um número e perguntamos se existe uma solução de tamanho no máximo .S G - S k kGSGSkk

No presente documento que provar que (R1), o problema é W -Hard, (R2) que admite um algoritmo de aproximação factor de dois em vez , e que (R3 ') assumindo uma hipótese um pouco mais forte que que existe um tal que o problema não admita um algoritmo de aproximação no tempo .2 k O ( 1 ) n O ( 1 ) F P T W [ 1 ] ϵ > 0 ( 1 + ϵ ) f ( k ) n O ( 1 )[1]2kO(1)nO(1)FPTW[1]ϵ>0(1+ϵ)f(k)nO(1)

daniello
fonte
6

Em [1], os autores provam que o MaxSAT parametrizado pela largura de clique (resp. Diversidade de vizinhos) do gráfico de incidência da fórmula CNF possui um FPT-AS (Esquema de Aproximação Tratável de Parâmetro Fixo), mas sabe-se que o MaxSAT parametrizou por largura de clique (resp. diversidade de vizinhos) é W [1] -hard.

O teorema baseia-se principalmente em um resultado de [2] que diz aproximadamente que gráficos de largura de clique limitada sem grandes panelinhas também têm largura de árvore limitada. Assim, eles cortam com inteligência a fórmula para que eles não tenham grande clique no gráfico de incidência e resolvam a fórmula reduzida no tempo do FPT usando um algoritmo conhecido para MaxSAT em largura de árvore limitada. Acho que essa abordagem também pode funcionar em outros problemas.

[1] Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, Tobias Mömke: complexidade e aproximabilidade de MAX-CSPs parametrizados. IPEC 2015

[2] Gurski, F., & Wanke, E. (2000, junho). A largura da árvore dos gráficos delimitados por largura da clique sem K n, n . No Workshop Internacional sobre Conceitos Teórico-Gráficos em Ciência da Computação (pp. 196-205). Springer, Berlim, Heidelberg.

holf
fonte
6

Em Coloração defeituosa , recebemos um gráfico e um número inteiro Δ e é solicitado que particionemos os vértices de G no número mínimo possível de classes de cores, de modo que cada classe induza um gráfico de grau máximo no máximo Δ . (Se Δ = 0, este problema é apenas coloração ).GΔGΔΔ=0

Em [1], mostramos o seguinte em relação a esse problema parametrizado por largura de árvore : (R1) o problema é W [1] -hard; (R2) o número mínimo de cores pode ser aproximado em 2 no tempo do FPT; (R3) não existe -approximation em FPT tempo, sob hipóteses normalizadas.(3/2ϵ)

[1] Rémy Belmonte, Michael Lampis e Valia Mitsou: coloração defeituosa parametrizada (aproximada). STACS '18.

Michael Lampis
fonte
5

O problema do corte k é remover um número mínimo de arestas para criar pelo menos k componentes. W [1] rígido quando parametrizado por k, mas admite uma aproximação 2 para qualquer k.

Chandra Chekuri
fonte
2
(2-ϵ)(2-δ)2O(k)nO(1)δ>0 0
5

(Esta pergunta foi feita há dois anos, mas postarei a resposta para outras pessoas que possam vê-la.)

kFfvocêfZ0 0CdFCkSFkϕ:CS|ϕ-1(f)|vocêffScCd(c,ϕ(C))W[2]khttps://arxiv.org/pdf/1708.04218.pdf )

Amir Nikabadi
fonte