Résolution exacte de la super chaîne

Que sait-on de la complexité exacte du problème de chaîne la plus courte? Peut-il être résolu plus rapidement que ? Existe-t-il des algorithmes connus qui résolvent la super chaîne la plus courte sans réduire au TSP? $O^*(2^n)$

UPD: supprime les facteurs polynomiaux. $O^*(\cdot)$

Le problème de superstring le plus court est un problème dont la réponse est la chaîne la plus courte qui contient chaque chaîne d'un ensemble donné de chaînes. La question porte sur l'optimisation de l'extension d'un célèbre problème NP-Shortest Superstring (Garey et Johnson, p.228).

cc.complexity-theory ds.algorithms graph-theory tsp exp-time-algorithms Alex Golovnev
la source

Qu'est-ce que "le problème des supercordes"?

Jeffε

Je voulais dire le problème de chaîne la plus courte, je l'ai résolu. Je vous remercie!

Alex Golovnev

Bon alors, quel est "le problème de supercord le plus court"? Je peux penser à plusieurs problèmes qui méritent ce nom, et quelques autres qui devraient être appelés "le problème de super-séquence le plus court " mais qui ne sont probablement pas en pratique. Donnez-nous un peu de contexte, s'il vous plaît!

Jeffε

Quel est votre problème? Par exemple, si vous recherchez la super chaîne la plus courte dans la fragmentation du génome, parce que la fragmentation du génome crée des graphiques de largeur d'arbre bornés, vous pouvez avoir un algorithme rapide, mais si vous êtes juste intéressé par des algorithmes plus rapides que les algorithmes disponibles, votre réponse est non, sauf que vous pouvez avoir un algorithme plus rapide dans TSP (en raison de la réduction simple), il y a aussi

algorithme dans les graphiques de largeur d'arbre délimités localement.

O^{*} (2^{\sqrt{n}})

$O^*(2^{\sqrt n})$

Saeed

@AlexGolovnev, Oui, vous avez raison, c'est ATSP, mais pour la largeur d'arbre bornée, je pense qu'il est bon de voir cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 ou si vous voulez en savoir plus à leur sujet, c'est bien aussi voir algorithmique méta-théorème

Saeed

Réponses:

En supposant que les chaînes ont un polynôme de longueur en , alors oui, il y a au moins $n$ solution de temps. La raison en est la réduction bien connue du problème de superstring commun le plus court à ATSP avec des poids entiers de taille polynomiale, que vous pouvez à votre tour résoudre par interpolation polynomiale si vous pouvez compter les cycles hamiltoniens dans un multigraphe dirigé. Ce dernier problème a un $2^{n-\Omega(\sqrt{n/\log n})}$ solution de temps. Björklund 2012 $2^{n-\Omega(\sqrt{n/\log n})}$

La réduction de l'ATSP avec les poids pour chaque paire de sommets au comptage de cycle hamiltonien se déroule comme suit: $w_{uv}$ $u,v$

Pour , où est une borne supérieure sur toutes les sommes de poids dans l'instance ATSP, construisez un graphique où vous remplacez chaque poids par arcs à partir de à . $r=1,2,\cdots,w_\mbox{sum}$ $w_\mbox{sum}$ $n$ $G_r$ $w_{uv}$ $r^{w_{uv}}$ $u$ $v$

En résolvant le comptage du cycle hamiltonien pour chaque , vous pouvez, par interpolation polynomiale, construire un polynôme avec égal au nombre de tours TSP dans le graphique d'origine du poids . Ainsi, la localisation du plus petit tel que est non nul résout le problème. $G_r$ $\sum_{l=0}^{w_\mbox{sum}} a_lr^l$ $a_l$ $l$ $l$ $a_l$

Andreas Björklund
la source

Merci beaucoup! Je ne connaissais pas ce lien avec le comptage du cycle hamiltonien.

Alex Golovnev

@AlexGolovnev: Mais la réduction est plus ou moins la même que dans par exemple le résultat Kohn, Gottlieb, Kohn que vous avez cité dans votre propre réponse? Il s'agit d'une simple intégration de la semi-somme minimale sur les entiers. Quoi qu'il en soit, merci de m'avoir fait réaliser que la prochaine version de mon article devrait le dire explicitement.

Andreas Björklund

J'ai étudié le problème et j'ai trouvé des résultats. La chaîne commune la plus courte (SCS) peut être résolue dans le temps avec seulement un espace polynomial ( Kohn, Gottlieb, Kohn ; Karp ; Bax, Franklin ). $2^n$

L'approximation la plus connue est (Paluch). $2\frac{11}{30}$

La meilleure approximation connue de la compression est (Paluch). $3\over4$

Si SCS peut être approximé par un facteur sur l'alphabet binaire, alors il peut être approximé par un facteur sur n'importe quel alphabet ( Vassilevska-Williams ). $\alpha$ $\alpha$

SCS ne peut être approché avec un rapport meilleur que moins que P = NP ( Karpinski, Schmied ). $1.0029$

La compression maximale ne peut être approchée avec un rapport meilleur que moins que P = NP ( Karpinski, Schmied ). $1.0048$

Je serais reconnaissant pour tout ajout et suggestion.

Alex Golovnev
la source

Voici le problème de super chaîne le plus court: on vous donne chaînes sur un alphabet et vous voulez trouver la chaîne la plus courte sur qui contient chaque comme sous-séquence de caractères consécutifs, c'est-à-dire une sous-chaîne. $n$ $s_1,\ldots, s_n$ $\Sigma$ $\Sigma$ $s_i$

Lorsque nous parlons d'algorithmes exacts pour le problème, trouver la longueur de la chaîne la plus courte équivaut à trouver la compression maximale qui est la somme de tous les chevauchements de chaînes consécutifs dans la chaîne supérieure, c'est-à-dire . $L$ $C$ $C=\sum_i |s_i|-L$

Autant que je sache, l'algorithme exact le plus rapide pour les supercordes les plus courtes s'exécute dans ( ) où est le nombre de chaînes. Il s'agit d'un algorithme de programmation dynamique simple similaire à l'algorithme de programmation dynamique pour le chemin le plus long (et d'autres problèmes): $O^*$ $2^n$ $n$

Pour chaque sous-ensemble de chaînes et chaîne dans nous calculons la compression maximale sur toutes les super- chaînes sur où est la première chaîne apparaissant dans la super-chaîne, la stockant sous la forme C (( )). Pour ce faire, nous traitons d'abord tous les sous-ensembles avec un seul élément, puis nous construisons les valeurs C (( )) pour les sous-ensembles sur chaînes à partir de celles sur chaînes. Plus précisément: $S$ $v$ $S$ $S$ $v$ $v,S$ $v,S$ $S$ $k$ $k-1$

Pour chaque chaîne nous examinons tous les sous-ensembles sur chaînes qui n'incluent pas et fixons la valeur pour ( ) au maximum sur les chaînes dans de la somme du maximum chevauchement de avec avec C (( )). $u$ $S'$ $k-1$ $u$ $u,{u}\cup S'$ $v$ $S'$ $u$ $v$ $v,S'$

L'exécution finale n'est pas supérieure à O ( ) où est la longueur de chaîne maximale. $n^2 2^n + n^2 l$ $l$

Il y a de meilleurs algorithmes si vous supposez que est petit, ou que les chevauchements par paire sont petits, la taille de l'alphabet est petite, etc., mais je ne connais aucun algorithme plus rapide que . $l$ $2^n$

virgi
la source

OP connaît l' algorithme

, il a demandé une solution plus rapide.

O^{*} (2^{n})

$O^*(2^n)$

Saeed

comme je l'ai dit, je ne crois pas qu'une solution plus rapide soit connue.

virgi

@virgi, merci beaucoup! Votre algorithme est très sympa. Mais je pense que le principe d'inclusion-exclusion nous donne même un algorithme

avec un espace polynomial pour le problème de Superstring. Je suis vraiment intéressant dans les algorithmes plus rapides, peut-être avec quelques contraintes (petit alphabet, réponse courte, etc.). Merci beaucoup!

O^{*} (2^{n})

$O^*(2^n)$

Alex Golovnev