Un resultado fundamental en la complejidad parametrizada de los problemas gráficos es que la CUBIERTA VERTEX parametrizada por el tamaño de la solución es manejable con parámetros fijos (FPT). Por otro lado, cuando se parametriza mediante el "parámetro dual" , se convierte en equivalente a SET INDEPENDIENTE parametrizado por tamaño de solución (porque cualquier cubierta de vértice es el complemento de un conjunto independiente), y por lo tanto es W [1] -duro.| V ( G ) | - k
Aunque esto parece menos natural, estoy interesado en la complejidad parametrizada de VERTEX COVER para el parámetro . Este es un parámetro más grande que . ¿VERTEX COVER FPT es para este parámetro?| V ( G ) | - k
Nota: También estoy interesado en parametrizaciones similares para otros problemas de gráficos (p. Ej., DOMINATOR SET). El único lugar donde he visto los dos tipos de parámetros duales estudiados es para el problema de la hipergrafía TEST COVER en el artículo de 2012 " Estudio parametrizado del problema de la cubierta de prueba " de Crowston, Gutin, Jones, Saurabh y Yeo. (también en arXiv )
Editar (04/12/2016): Esta parametrización también se estudia para el otro problema de hipergrafía SET HITTING en los Kernels de papel de 2011 para parametrizaciones por debajo del límite superior del conjunto de golpes y los problemas del conjunto dominante dirigido por Gutin, Mones y Yeo ( arXiv enlace ).
fuente
fuente