L'étude de la complexité de calcul des problèmes par rapport à plus d'un paramètre.
On sait que certains problèmes sont indécidables, mais il est néanmoins possible de progresser dans leur résolution. Par exemple, le problème d'arrêt est indécidable, mais des progrès pratiques peuvent être réalisés dans la création d'outils permettant de détecter les boucles infinies potentielles...
Je m'intéresse à la complexité paramétrée de ce que j'appellerai le problème d'ensemble d-dimensionnel: donné un espace de plage (c'est-à-dire un ensemble système / hypergraphe) S = (X, R) ayant une dimension VC au plus d et a entier positif k, X contient-il un sous-ensemble de taille k qui touche...
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Définissons maintenant les ensembles de toutes les entrées avec la complexité de Kolmogorov , et définissons la séquence Ici est la séquence de...
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
La largeur d'arbre joue un rôle important dans les algorithmes FPT, en partie parce que de nombreux problèmes sont paramétrés FPT par la largeur d'arbre. Une notion connexe, plus restreinte, est celle de largeur de chemin. Si un graphe a une largeur de chemin , il a également une largeur d'arbre au...
Soit 0 ≤ p ≤ 10≤p≤10\le p\le 1 et considérons le problème de décision CLIQUE p entrée: nombre entier s , graphe G avec t sommets et bords Question: ne contient une clique sur au moins les sommets?pp_p sssggGttt⌈ p ( t2) ⌉⌈p(t2)⌉\lceil p\binom{t}{2} \rceil ggGsss Une instance de CLIQUE contient une...
Que faire si l'on sait quelque chose sur la complexité paramétrée du calcul du nombre d'intersection d'un graphe (le plus petit nombre de cliques nécessaires pour couvrir tous ses bords)? Il est connu depuis longtemps pour être NP-complet, et c'est évidemment FPT car il a un noyau: si vous pouvez...
Étant donné un graphe non dirigé à nnn sommets, quelle est la limite d'exécution la plus connue pour trouver un sous-graphe qui est un k×kk×kk\times k -biclique? Existe-t-il des algorithmes paramétrés plus rapides que l'algorithme de temps consiste à "deviner" un côté de la biclique et à voir s'il...
Comme tout le monde le sait, le célèbre livre de Garey et Johnson (et bien d'autres) fournit une excellente référence pour la technique de réduction en milieu classique. Existe-t-il des enquêtes ou des livres sur le thème de la technique de réduction dans l'algorithme paramétré, disons la réduction...
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...
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...
La hiérarchie est une hiérarchie de classes de complexité en complexité paramétrée, voir le Complexity Zoo pour les définitions. Une définition alternative définit utilisant la définissabilité pondérée de Fagin pour les logique du premier ordre, voir le manuel de Flum et Grohe...
Motivation: Un co-auteur édite un manuscrit et j'aimerais voir un résumé clair des éditions. Toutes les « diff » -comme outils ont tendance à être inutile si vous êtes à la fois du texte déplacerez (par exemple, la réorganisation de la structure) et faire des modifications locales. Est-il vraiment...
La largeur d'arbre et la largeur de chemin sont des paramètres populaires, mesurant la proximité d'un graphique avec un arbre ou un chemin, respectivement. En effet, il semble que la largeur d'arbre soit si populaire qu'elle figure dans de nombreux articles, livres et notes de cours qui donnent...
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...
Le poidsd'une chaîne binaire est le nombre de uns dans la chaîne. Que se passe-t-il si nous sommes intéressés à calculer une fonction monotone sur des entrées avec quelques-unes?|x||x||x|x∈{0,1}nx∈{0,1}nx\in\{0,1\}^n On sait que décider si un graphe a une -clique est difficile pour les circuits...
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...
Soit et notons G k l'ensemble de tous les graphes qui peuvent être incrustés sur une surface du genre k de telle sorte que tous les sommets soient situés sur la face externe . Par exemple, G 0 est l'ensemble des graphes planaires externes. La largeur d'arbre des graphes dans G k peut-elle être...
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...