Connaissez-vous des problèmes qui sont durs W [1] même pour les graphes de degrés bornés? La dimension métrique est difficile sur les graphiques avec un degré au plus 3, mais elle est W [2] -hard. Red-Blue Nonblocker était auparavant W [1] -hard sur les graphiques de degrés bornés, mais il y avait...
Dans la complexité paramétrée, les gens utilisent la réduction à paramètres fixes (FPT) pour prouver la dureté W [t]. Théoriquement, une réduction FPT n'est pas une réduction du temps polynomial, car elle peut s'exécuter de façon exponentielle dans le paramètre k. Mais dans la pratique, toutes les...
Suite aux questions équivalentes concernant NP-Completeness (voir la question de poids et la question dirigée ), je me demandais comment les problèmes paramétrés sont affectés par ces attributs. Quels problèmes de graphes durs sont W [ 1 ] -Dur sur les graphes dirigés, mais les paramètres fixes...
Le problème paramétré k-FLIP SAT est défini comme suit: Entrée: une formule 3-CNF avec n variables et une affectation de vérité \ sigma: [n] \ à \ {0,1 \} Paramètre: k Question: pouvons-nous transformer l'affectation \ sigma en une affectation satisfaisante \ sigma ' pour \ varphi retourner la...
Supposons que est un langage paramétré par rapport à un alphabet . La tranche de est , l'ensemble des instances de qui ont le paramètre . La classe de complexité contient les langages paramétrés tels que pour chaque , éventuellement avec un algorithme différent et un temps d'exécution polynomial...
Je suis un chercheur qui travaille dans la théorie des algorithmes et de la complexité, j'utilise la complexité paramétrée dans une certaine mesure. Il me semble que les chercheurs en complexité paramétrée sont très actifs (je ne veux pas dire que d'autres ne le sont pas) en termes de nombre de...
Soit une famille de sous-ensembles d'éléments d'un univers fini d'objets. Une famille de sous-ensembles d'éléments de , avec , est un - ensemble de frappes de si pour chaque il existe au moins un ensemble tel que .FFFdddUUUHHHkkkUUU1≤k<d1≤k<d1 \le k < d(k,d)(k,d)(k,d)FFFV∈FV∈FV \in FW∈HW∈HW...
Dans une question précédente, Algorithme paramétré pour trouver des bicliques , je me suis demandé s'il y avait des algorithmes paramétrés rapides pour trouver un -biclique dans un graphe de sommets n et j'ai appris qu'il était ouvert s'il était FPT par rapport à k . Est-ce la même chose pour le...