Problèmes de graphes durs sous-exponentiellement résolubles

À la lumière des résultats récents d'Arora, Barak et Steurer, Algorithmes sous-exponentiels pour les jeux uniques et les problèmes connexes , je suis intéressé par les problèmes de graphes qui ont des algorithmes de temps sous-exponentiels mais qui ne sont pas résolus polynomialement. Un exemple célèbre est l'isomorphisme de graphe qui a un algorithme sous-exponentiel de exécution. Un autre exemple est le problème log-Clique qui est résoluble en temps quasi-polynomial ( ). n O ( log n $2^{O(n^{1/2} \log n)}$$n^{O(\log n)}$

Je cherche des exemples intéressants et de préférence une référence à des enquêtes sur des problèmes de graphes durs sous-exponentiels (pas nécessairement complétés). Y a-t-il également des problèmes de graphes complets avec les algorithmes de temps sous-exponentiels?N $NP$$NP$

Impagliazzo, Paturi et Zane ont montré que l'hypothèse de temps exponentielle implique que Clique, k-Colorability et Vertex Cover ont besoin de temps.$2^{\Omega(n)}$

Soit dit en passant, le problème de Max Clique, en général, peut être résolu dans le temps oùNest la taille de l'entrée.$2^{\tilde O(\sqrt N)}$$N$

Ceci est trivial si le graphe est représenté via une matrice d'adjacence, car alors , et une recherche par force brute prendra 2 O ( | V | ) .$N=|V|^2$$2^{O(|V|)}$

Mais on peut obtenir la même borne même si le graphe est représenté par des listes d'adjacence, via un algorithme de temps d'exécution . Pour voir comment, obtenons un2 ˜ O ($2^{\tilde O(\sqrt{|V| + |E|})}$algorithme de temps pour le problème de décision NP-complet dans lequel on nous donne un grapheG=(V,E)etket nous voulons savoir s'il existe une clique de taille≥k.$2^{\tilde O(\sqrt{|V| + |E|})}$$G=(V,E)$$k$$\geq k$

L'algorithme supprime simplement tous les sommets de degré et les arêtes qui les touchent, puis recommence, et ainsi de suite, jusqu'à ce qu'il nous reste un sous-graphe induit par des sommets sur un sous-ensemble V ′ de sommets, chacun de degré ≥ k , ou avec un graphique vide. Dans ce dernier cas, nous savons qu'aucune clique de taille ≥ k ne peut exister. Dans le premier cas, nous effectuons une recherche par force brute à peu près dans le temps | V ′ | k . Notez que | E | ≥ k ⋅ | V ′ | / 2 et k $< k$$V'$$\geq k$$\geq k$$|V'|^k$$|E| \geq k\cdot |V'| /2$, pour que | E | ≥ k 2 / 2 , et ainsi une recherche de force brutecoursexécution danstemps | V ′ | k s'exécute en fait dans le temps 2 O ( $k\leq |V'|$$|E| \geq k^2/2$$|V'|^k$.$2^{O(\sqrt{|E|} \cdot \log |V|)}$

Puisque chaque graphe planaire sur sommets a une largeur d'arbre O ( $n$, tous les problèmes qui peuvent être résolus en tempsO∗(2 O ( k ) )pour les graphiques de largeur d'arbre au plus ~k(il y a BEAUCOUP de ces problèmes) ont des algorithmes sous-exponentiels sur les graphiques planaires en calculant un facteur constant approximation de la largeur d'arbre en temps polynomial (par exemple en calculant la largeur de branche avec l'algorithme ratcatcher) puis en exécutant l'algorithme de largeur d'arbre, ce qui entraîne des temps d'exécution de la formeO∗(2 O ( $O(\sqrt{n})$$O^*(2^{O(k)})$$k$pour les graphes surnsommets. Les exemples sont Planar Independent Set et Planar Dominating Set, qui sont bien sûr NP-complets.$O^*(2^{O(\sqrt{n})})$$n$

Il existe un lien étroit entre la solvabilité temporelle sous-exponentielle (SUBEPT) et la tractabilité à paramètres fixes (FPT). Le lien entre eux est fourni dans l'article suivant.

Un isomorphisme entre théorie de la complexité sous-exponentielle et paramétrisée , Yijia Chen et Martin Grohe, 2006.

En bref, ils ont introduit une notion appelée cartographie de miniaturisation , qui mappe un problème paramétré dans un autre problème paramétré ( Q , κ ) . En visualisant un problème normal comme un problème paramétré par la taille d'entrée, nous avons la connexion suivante. (Voir le théorème 16 dans l'article)$(P,\nu)$$(Q,\kappa)$

Théorème . est en SUBEPT ssi ( Q , κ ) est en FPT.$(P,\nu)$$(Q,\kappa)$

Faites attention aux définitions ici. Normalement, nous considérons le problème -clique comme paramétré en k , il n'y a donc pas d'algorithme de temps sous-exponentiel pour lui en supposant l'hypothèse de temps exponentielle. Mais ici, nous laissons le problème être paramétré par la taille d'entrée O ( m + n ) , donc le problème peut être résolu en 2 O ( $k$$k$$O(m+n)$, qui est un algorithme de temps sous-exponentiel. Et le théorème nous dit que leproblème dek-clique est un paramètre fixe traitable sous la torsion du paramètrek, ce qui est raisonnable.$2^{O(\sqrt{m}\log m)}$$k$$k$

En général, les problèmes dans SUBEPT sous SERF-réductions (familles de réduction sous-exponentielles) peuvent être transformés en problèmes dans FPT sous FPT-réductions. (Théorème 20 de l'article) De plus, les connexions sont encore plus fortes car elles ont fourni un théorème d'isomorphisme entre toute une hiérarchie de problèmes dans la théorie de la complexité du temps exponentielle et la théorie de la complexité paramétrée. (Théorème 25 et 47) Bien que l'isomorphisme ne soit pas complet (il manque des liens entre eux), il est toujours agréable d'avoir une image claire de ces problèmes, et nous pouvons étudier des algorithmes de temps sous-exponentiels via une complexité paramétrée.

Voir l' enquête de Jörg Flum et Martin Grohe, avec Jacobo Torán, le rédacteur de la colonne complexité, pour plus d'informations.

un autre exemple peut être le jeu Cop and Robber, qui est NP-difficile mais résoluble en temps sur des graphiques avec n sommets. Notice bibliographique BibTeX en XML Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan: Poursuivre un voleur rapide sur un graphique. Théor. Comput. Sci. 411 (7-9): 1167-1181 (2010)$2^{o(n)}$

Le meilleur algorithme d'approximation pour la clique donne un facteur d'approximation incroyablement mauvais (rappelons que le facteur d'approximation de n est trivial).$n/\text{polylog } n$$n$

Il existe des résultats d'approximation de la dureté sous diverses hypothèses de dureté qui ne correspondent pas tout à fait à cela, mais donnent toujours une dureté de . Personnellement, je crois que l' approximation n / polylog  n pour la clique est aussi bonne que les algorithmes polynomiaux ne le feraient jamais.$n^{1-o(1)}$$n/\text{polylog } n$

Mais l'approximation de pour clique peut facilement être effectuée en temps quasi polynomial.$n/\text{polylog } n$

$2^{\Omega(n)}$$2^{\Omega(N^\epsilon)}$$N=n^{1/\epsilon}$$\epsilon$