Точное решение суперструны

18

Что известно о точной сложности самой короткой проблемы суперструн? Может ли это быть решено быстрее, чем O(2n) ? Существуют ли известные алгоритмы, которые решают кратчайшую суперструну без сокращения до TSP?

UPD: подавляет полиномиальные факторы.O()

Самая короткая проблема суперструн - это проблема, ответом которой является самая короткая строка, которая содержит каждую строку из заданного набора строк. Речь идет о расширении оптимизации известной NP-сложной задачи Shortest Superstring (Garey and Johnson, p.228).

Алекс Головнев
источник
5
Что такое "проблема суперструн"?
Джеффс
Я имел в виду проблему самой короткой суперструны, я ее исправил. Спасибо!
Алексей Головнев
10
Хорошо, тогда какова "самая короткая проблема суперструн"? Я могу вспомнить несколько проблем, которые заслуживают этого названия, и еще несколько, которые следует называть «самой короткой проблемой суперпоследовательности », но, вероятно, их нет на практике. Дайте нам немного контекста, пожалуйста!
Джеффс
1
Какая у вас проблемная область? Например, если вы ищете самую короткую суперструну в фрагментации генома, поскольку фрагментация генома создает ограниченные графы ширины дерева, вы можете использовать быстрый алгоритм, но если вы просто заинтересованы в более быстрых, чем доступные алгоритмах, ваш ответ - нет, за исключением того, что вы можете иметь более быстрый алгоритм в TSP (из-за простого сокращения), также есть алгоритм в локально ограниченных графах ширины дерева. O(2n)
Саид
1
@AlexGolovnev, да, вы правы, это ATSP, но для ограниченной ширины дерева я думаю, что приятно видеть cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2 или, если вы хотите узнать больше о них, тоже хорошо, посмотрите алгоритмический мета теорема
Саид

Ответы:

5

Предполагая, что строки имеют полином длины от , тогда да, по крайней мере, 2 n - Ω ( nвремя решения. Причина - хорошо известное сокращение от самой короткой общей проблемы суперструн до ATSP с целочисленными весами полиномиального размера, которую вы, в свою очередь, можете решить с помощью полиномиальной интерполяции, если вы можете считать гамильтоновы циклы в ориентированном мультиграфе. Последняя проблема имеет2n-Ω(2nΩ(n/logn)время решения. Бьорклунд 20122nΩ(n/logn)

Переход от ATSP с весами для каждой пары вершин u , v к гамильтонову циклу происходит следующим образом:wuvu,v

Для , где w sum - верхняя граница для всех сумм n весовых коэффициентов в экземпляре ATSP, построим один граф G r, где вы заменяете каждый весовой коэффициент w u v на r w u v дуг из у к v .r=1,2,,wsumwsumnGrwuvrwuvuv

Решая подсчет гамильтонов цикл для каждого , можно с помощью полиномиальной интерполяции построить многочлен Х ш суммы л = 0 л г л с в л равна числу TSP туров в первоначальном графике веса л . Следовательно, поиск наименьшего l такого, что a l отличен от нуля, решает проблему.Grl=0wsumalrlalllal

Андреас Бьёрклунд
источник
Большое спасибо! Я не знал этой связи с гамильтоновым подсчетом циклов.
Алексей Головнев
@AlexGolovnev: Но сокращение более или менее такое же, как, например, в случае с Коном, Готлибом, Коном, который вы указали в своем собственном ответе? Это простое вложение полукольца с минимальной суммой на целые числа. В любом случае, спасибо, что заставили меня понять, что в следующей версии моей статьи это должно быть прямо указано.
Андреас Бьёрклунд,
8

Я изучил проблему и нашел некоторые результаты. Кратчайшая общая суперструна (SCS) может быть решена за время с использованием только полиномиального пространства ( Кон, Готтлиб, Кон ; Карп ; Бакс, Франклин ).2n

Самое известное приближение (Палуч).21130

Самое известное приближение сжатия составляет (Палуч).34

Если SCS может быть аппроксимирован фактором по двоичному алфавиту, то он может быть аппроксимирован фактором α по любому алфавиту ( Василевская-Уильямс ).αα

SCS не может быть аппроксимирована с отношением лучше, чем если P = NP ( Karpinski, Schmied ).1.0029

Максимальное сжатие не может быть аппроксимировано с коэффициентом, превышающим если P = NP ( Karpinski, Schmied ).1.0048

Буду благодарен за любые дополнения и предложения.

Алекс Головнев
источник
5

Вот кратчайшая проблема суперструн: вам дано строк s 1 , , s n над некоторым алфавитом Σ, и вы хотите найти самую короткую строку над Σ, которая содержит каждый s i как подпоследовательность последовательных символов, то есть подстроку.ns1,,snΣΣsi

Когда мы говорим о точных алгоритмах для задачи, нахождение длины самой короткой суперструны эквивалентно нахождению максимального сжатия C, которое является суммой всех последовательных перекрытий строк в конечной суперструне, то есть C = i | с я | - L .LCC=i|si|L

Насколько я знаю, самый быстрый точный алгоритм для самой короткой суперструны работает в ( 2 n ), где n - количество строк. Это простой алгоритм динамического программирования, аналогичный алгоритму динамического программирования для самого длинного пути (и других задач):O2nn

Для каждого подмножества строк и строки v в S мы вычисляем максимальное сжатие по всем суперструнам по S, где v - первая строка, появляющаяся в суперструне, сохраняя ее как C (( v , S )). Мы делаем это, сначала обрабатывая все подмножества только с одним элементом, а затем собирая значения C (( v , S )) для подмножеств S в k строках из тех, что в k - 1 строках. В частности:SvSSvv,Sv,SSkk1

Для каждой строки мы рассматриваем все подмножества S на k - 1 строках, которые не включают в себя u, и устанавливаем значение для ( u , uS ) максимального значения над строками v в S суммы максимума перекрытие U с V с C (( VuSk1uu,uSvSuv )).v,S

Конечное время выполнения не более O ( n22n+n2l ), где - максимальная длина строки.l

Есть лучшие алгоритмы, если вы предполагаете, что мало, или попарные наложения малы, размер алфавита маленький и т. Д., Но я не знаю ни одного алгоритма, который быстрее, чем 2 n .l2n

Virgi
источник
5
ОП знает алгоритм , он попросил более быстрого решения. O(2n)
Саид
2
как я уже сказал, я не верю, что известно более быстрое решение.
Вирджи
1
O(2n)