algorithmes pour les problèmes paramétrés où le temps d'exécution est polynomial dans la taille d'entrée, mais dépend arbitrairement du paramètre
En complexité paramétrée, ⊆ W [ 2 ] ⊆ … ⊆ W [ P ] . On suppose que chacune des enceintes est appropriée.F P T ⊆ W [1]FPT⊆W[1]\mathsf{FPT} \subseteq \mathsf{W}[1] ⊆W[2]⊆W[2]\subseteq \mathsf{W}[2] ⊆…⊆W[P]⊆…⊆W[P]\subseteq \ldots \subseteq \mathsf{W}[P] Si alors P = W [ P ]...
Je voudrais en savoir plus sur la complexité paramétrée (à la fois du côté algorithmique et du côté de la dureté). Quels livres / notes de cours puis-je lire à ce
Actuellement, je fais une étude documentaire sur le problème d'isomorphisme graphique (GI). J'aimerais connaître quelques questions ouvertes concernant les points suivants Quels sont les paramètres du graphique pour lesquels la tractabilité des paramètres fixes de l'IG est un problème ouvert. Quels...
Quand on nous donne une décomposition arborescente d'un graphe de largeur , il y a plusieurs façons de le rendre "agréable". En particulier, il est connu qu'il est possible de le transformer en une décomposition d'arbre où l'arbre est binaire et sa hauteur est . Ceci peut être réalisé tout en...
Le problème du kkk cycle est le suivant: Instance: Un graphe non orienté GGGavec nnn sommets et jusqu'à arêtes.(n2)(n2)n \choose 2 Question: Existe-t-il un (bon) kkk cycle dans GGG ? Contexte: Pour tout k fixe kkk, nous pouvons résoudre un cycle de 2k2k2k en temps O(n2)O(n2)O(n^2) . Raphael Yuster,...
Etant donné un graphe, , je veux trouver un optimal r -domination pour G . C'est, je veux un sous - ensemble S de V tel que tous les sommets de G sont à une distance d'au plus r de un sommet en S , tout en minimisant la taille S .G=(V,E)G=(V,E)G = (V, E)rrrGGGSSSVVVGGGrrrSSSSSS D'après ce que j'ai...
Vertex Cover peut être facilement réduit en jeu indépendant et vice versa. Cependant, dans un contexte de complexité paramétrée, l'ensemble indépendant est plus difficile que Vertex Cover. Un noyau avec sommets existe pour Vertex Cover, mais Independent Set est W 1 hard.2k2k2k Comment la nature de...
Les paramètres fixes et l'approximation sont des approches totalement différentes pour résoudre des problèmes difficiles. Ils ont une motivation différente. L'approximation recherche un résultat plus rapide avec une solution approximative. Le paramètre fixe recherche une solution exacte avec une...
Dans la définition de la tractabilité à paramètres fixes (forts), la limite de temps est une expression de la forme où l'instance d'entrée est ( x , k ) avec le paramètre k , p est un polynôme et f est une fonction calculable .F( k ) .p ( | x | ) ,F(k).p(|X|),f(k).p(|x|),( x , k...
Soit une formule 2CNF et k un entier non négatif. Il est prouvé dans cet article que le problème de décider si l'on peut supprimer au plus k clauses pour rendre satisfaisable, est un paramètre fixe traitable, où est le paramètre. Ma question est de savoir s'il existe des travaux qui généralisent ce...
Dans l'article de Stephen Cook sur le problème P vs NP [1], il déclare ce qui suit [2]: Thèse de faisabilité: Un problème naturel a un algorithme réalisable s'il a un algorithme polynomial. Ma question est, que veut-il dire exactement (ou en général, qu'est-ce que l'on entend) par "un problème...
Wikipédia écrit: FPT contient les problèmes traitables à paramètres fixes, qui sont ceux qui peuvent être résolus dans le temps pour une fonction calculable f . En règle générale, cette fonction est considérée comme une seule exponentielle, comme 2 O ( k ), mais la définition admet des fonctions...
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...
Conjecture de Berman – Hartmanis: tous les langages NP-complets se ressemblent, en ce sens qu'ils peuvent être liés les uns aux autres par des isomorphismes polynomiaux temporels [1]. Je suis intéressé par une version plus fine du "temps polynomial", c'est-à-dire si nous utilisons des réductions...
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...