Жадная гипотеза в задаче о кратчайшей общей надстроке и её обобщения тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Николаев Максим Сергеевич

• Николаев Максим Сергеевич
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Николаев Максим Сергеевич

Введение

Глава 1. Предварительные сведения

1.1 Строки, перекрытия, граф перекрытий

1.2 Циклы и покрытия циклами

1.3 Индуцированные вхождения

1.4 Иерархический граф

Глава 2. Жадный иерархический алгоритм является жадным

Глава 3. Все жадные алгоритмы эквивалентны

3.1 Процедура возмущения

3.2 Эквивалентность детерминизаций

Глава 4. Локально жадный алгоритм является равномерно

4-приближенным

4.1 Граф псевдо-перекрытий

4.2 Число индуцированных вхождений вместо длин

4.3 Доказательство Теоремы

Глава 5. Из гипотезы обвала для к копий следует равномерная ^-приближенность жадного алгоритма

5.1 Доказательство Теоремы

5.2 Доказательство Теорем 6 и

Глава 6. Нижние оценки

6.1 Локально жадный алгоритм является по крайней мере З-приближенным

6.2 Жадный алгоритм является по крайней мере равномерно 2.5-приближенным

Глава 7. Более простые доказательства

Стр.

7.1 Жадный алгоритм является ^-приближенным для компрессии

7.2 Гипотеза обвала верна для случая входных строк длины не больше трех

Заключение

Список литературы

Список рисунков

Список таблиц

Введение диссертации (часть автореферата) на тему «Жадная гипотеза в задаче о кратчайшей общей надстроке и её обобщения»

Введение

Актуальность работы и степень ее проработанности. Данная работа посвящена анализу приближенных алгоритмов для задачи о кратчайшей общей надстроке. В этой задаче для множества входных строк S = {si,... , sn} требуется найти кратчайшую строку, содержащую каждую из них в качестве подстроки. Эта задача имеет, с одной стороны, прикладное значение, например, в задаче сборки генома (см. [1; 2]): современные технологии могут извлекать только сравнительно короткие последовательности нуклеотидов, поэтому возникает задача восстановления ДНК по большому набору таких последовательностей. С другой стороны, эта задача интересна в теории сложности вычислений, так как является частным случаем задачи поиска во взвешенном ориентированном графе гамильтонова пути наибольшего веса, но при этом имеет богатую дополнительную структуру.

Для непустых строк s и £ (не обязательно различных) через ov(s,t) будем обозначать их перекрытие, то есть строку у наибольшей дайны такую, что s = ху и t = уz для некоторых непустых строк х и z. Строку xyz при этом будем называть слиянием sut. Например, перекрытие строк утконос и носорог равно нос, а их слияние равно утконосорог.

В дальнейшем всегда будет предполагаться, что никакая из входных строк не является подстрокой другой входной строки, так как такие строки можно эффективно найти и исключить из входного множества, и всякая надстрока для полученного множества будет надстрокой для исходного. В этом случае задача о надстроке сводится к задаче поиска такой перестановки индексов g : {1 ,...,п} ^ {1 ,...,п}, что после слияния соседних строк в кортеже (sCT(1),..., So-(n)) получается надстрока наименьшей длины. Через s (g) обозначим над строку, получающуюся описанным выше образом из перестановки индексов Œ. Любой алгоритм А, который строит надстроку, последовательно сливая входные строки, индуцирует перестановку g а такую, что итоговая надстрока равна s(ga)-

Задача о кратчайшей общей надстроке является АРХ-трудной [3], в частности, для нее нет эффективного алгоритма построения (1 + е)-приближения для некоторого £ > 0, если P = NP. Наилучшая на данный момент нижняя оценка на £ равн а 332 и получена в работе [ ]. По этой причине активно и с-

сдедуются практические алгоритмы для нахождения приближенного решения. По-видимому, наиболее простым таким алгоритмом является жадный алгоритм, действующий следующим образом: пока имеется более двух строк, он выбирает две из них с наибольшим перекрытием и сливает.

Жадный алгоритм не является детерминированным, так как может слить любую пару строк с максимальным перекрытием, и это может сильно повлиять па финальный результат. В качестве примера рассмотрим набор 5 = {аЪте, Ъте+1, Ътес}. Для пего жадный алгоритм может построить как оптимальное решение аЪте+1с, так и асимптотически в два раза более длинное решение аЪпсЪп+1 в зависимости от конкретного правила разрешения ничьих, то есть правила, по которому выбирается конкретная пара среди пар с максимальными перекрытиями. Этот пример показывает, что коэффициент приближения жадного алгоритма не меньше двух, и Тархио и Укконен в своей работе 1988 года [5] предположили, что он в точности равен двум, вне зависимости от правила разрешения ничьих. Эта гипотеза получила название Жадной гипотезы.

На данный момент, спустя почти сорок лет, эта гипотеза остается открытой. Первая константная верхняя оценка на коэффициент приближения жадного алгоритма, равная четырем, была получена в 1991 году Блумом, Цзяном, Ли, Тромпом и Яннакакисом [3]. Эта оценка была улучшена до 3,5 Каплаиом и Шафриром в 2005 году [6], и следующие два улучшения: до 3,425 и до 3,396 соответственно, были получены Энгдертом, Матсакисом и Веселым в 2022 и 2023 годах в работах [7; 8]. Помимо этого известны следующие результаты, касающиеся жадного алгоритма:

— жадный алгоритм является ^-приближенным для другой функции качества решения компрессии [5; 9], где под компрессией понимается разность между суммарной длиной входных строк и длиной построенной надстроки;

— жадная гипотеза верна, если входные строки имеют длину не больше трех [10];

— жадная гипотеза верна, если входные строки имеют длину четыре [11];

— жадная гипотеза для случая бинарного алфавита эквивалентна случаю больших алфавитов [12].

Помимо жадного алгоритма исследуются и другие приближенные алгоритмы (см. Таблицу 1). Наилучшая известная на данный момент верхняя оценка,

Таблица 1 Известные верхние оценки на коэффициент приближения задачи

о кратчайшей общей над строке.

равная 2,466, была получена Энгдертом, Матсакисом и Веселым в упомянутой выше работе [8].

Большинство подходов для анализа задачи о кратчайшей надстроке используют так называемый граф перекрытий. В этом полном ориентированном графе с петлями вершинами являются входные строки, а вес ребра равен длине перекрытия соответствующих строк. Нетрудно показать, что задача поиска кратчайшей над строки эквивалентна задаче поиска в графе перекрытий га-мильтонова пути наибольшего веса, иначе говоря, задача о надстроке является частным случаем асимметричной задачи коммивояжера Max-ATSP. В общем случае Max-ATSP не может быть приближенно решена за полиномиальное время, если P = NP, в то же время в частном случае графов, являющихся графами перекрытий, эта задача может быть эффективно приближена с константным коэффициентом приближения. На данный момент отсутствует полная характеризация графов перекрытий, однако известны некоторые их свойства. Примерами таких свойств являются неравенство Монж.а [24],

Оценка Работа

Год

3,000 Blum, Jiang, Li, Tromp, Yannakakis [ ]

2,889 Teng, Yao [ ]

2,834 Czumaj, Gasieniec, Piotrow, Rytter [ ]

2,794 Kosaraju, Park, Stein [ ]

2,750 Armen, Stein [ ]

2,725 Armen, Stein [ ]

2,667 Armen, Stein [ ]

2,596 Breslauer, Jiang, Jiang [ ]

2,500 Sweedyk [ ]

2,500 Kaplan, Lewenstein, Shafrir, Sviridenko [ ]

2,500 Paluch, Elbassioni, van Zuylen [ ]

2,479 Mucha [ ]

2,475 Englert, Matsakis, Vesely [ ]

2,466 Englert, Matsakis, Vesely [ ]

1991

1993

1994 1994

1994

1995

1996

1997 1999 2005 2012 2013 2022 2023

неравенство треугольника и тройное неравенство [25]. Эти свойства не являются достаточными для доказательства жадной гипотезы [25; 26].

В 2014 году Головнев, Куликов и Михайлин в работе [27] предложили новую структуру данных иерархический граф. Этот граф является в некотором смысле обобщением графов де Брёйна [28] и содержит в себе больше информации о входных строках, чем граф перекрытий. Вершинами иерархического графа являются входные строки и все их подстроки, а ориентированные ребра имеют вид (рге^)^) и (б, Бий^я)}, где рге£(й) это й без последнего символа, а Бий^я) это й без первого символа. Иерархический граф назван так из-за того, что его вершины можно естественным образом расположить по уровням в соответствии с длинами соответствующих им строк (см. для примера рисунок 1а). В этом случае все ребра соединяют соседние уровни и делятся на два типа: верхние ребра имеют вид (рге£(й), я), нижние ребра имеют вид (й, Бий^)).

Всякая надстрока входного набора соответствует циклу (вообще говоря, не единственному), который проходит через пустую строку и входные строки. И наоборот, по всякому циклу, проходящему через пустую и входные строки, можно построить надстроку: для этого необходимо выйти из пустой строки и при прохождении по ребру вида (й, йа) дописывать символ а к построенному на данный момент решению (см. рисунки 16 и 1в). Таким образом задача о над-строке эквивалента задаче поиска в иерархическом графе кратчайшего цикла, проходяще 14) через пустую и входные строки: длина кратчайшей надстроки соответствует количеству верхних ребер в кратчайшем цикле и равна половине от его общей длины. Нетрудно видеть, что мультимножество ребер всякого такого цикла должно быть эйлеровым: оно должно быть связным, и входящая степень всякой вершины должна быть равна исходящей. Будем называть всякое эйлерово мультимножество ребер, которое проходит через пустую и входные строки, эйлеровым, решением,. Ребра эйлерова решения можно занумеровать (вообще говоря, не единственным образом) так, чтобы получился эйлеров цикл.

В 2018 году Головнев, Куликов, Логунов и Михайлин в препринте [29] предложили жадны,й иерархический алгоритмкоторый старается построить в иерархическом графе наиболее экономное эйлерово решение. Конкретнее, этот алгоритм проходит по уровням иерархического графа сверху вниз, на каждом уровне проходит по вершинам в лексикографическом порядке, и для вершины в добавляет в текущее решение ребра следующим образом:

Рисунок 1 — а) Иерархический граф для входного множества S = {aaa, cae, aec, eee}. б) Оптимальная надстрока для S это аааесаеее. Она имеет длину 9, соответствует перестановке (aaa, aec, cae, eee), и определяет цикл длины 18, показанный черным, в) Цикл, соответствующий жадному решению

ааасаесеее, имеет длину 20.

1. если s это входная вершина, то в решение добавляются ребра (pref(s),s) и (s, suff(s));

2. если s несбалансирована, то есть если ее исходящая степень не равна входящей, то алгоритм балансирует ее, добавляя подходящее количество ребер (pref(s), s) или (s, suff(s));

3. если s сбалансирована, то алгоритм ее пропускает, за исключением случая, когда она является последней в лексикографическом порядке вершиной некоторой уже построенной эйлеровой компоненты, ребра которой лежат выше этого уровня: в этом случае в решение добавляются ребра (pref(s),s) и (s, suff(s)).

Добавление ребер в пункте 1 необходимо, так как никакая входная строка s не является подстрокой другой, поэтому единственный способ посетить ее в иерархическом графе — это пройти через пару ребер (pref(s),s) и (s, suff(s)), а в пункте 3 необходимо для связи соответствующей эйлеровой компоненты с остальным решением.

В той же работе [29] была сформулирована гипотеза, что жадный иерархический алгоритм является 2-прибдиженным, а также предложен способ, как эту гипотезу можно попробовать доказать. Этот способ основан на еще одном алгоритме, алгоритме обвала, который принимает на вход некоторое эйлерово решение и пытается его обвалить: он проходит по вершинам иерархического графа в том же порядке, что и жадный иерархический, и заменяет каждую пару ребер вида (pref(s), s), (s, suff(ж)) на пару ребер вида (pref(s), suff(pref(s))),

(suff(pref(s)), suff(s)), если это не приводит к потере связности между входными строками и пустой строкой е. Если s это символ, то есть pref(s) = suff(s) = е, то ребра (e,s) и (s, е) не обваливаются, а удаляются. Таким образом алгоритм обвала сохраняет длину решения пока не дойдет до первого уровня, после чего решение будет только укорачиваться за счет выкинутых ребер.

Эмпирически было обнаружено, что если взять эйлерово решение, удвоить в нем ребра, после чего применить к нему алгоритм обвала, то получится одно и то же решение то самое, которое строит жадный иерархический алгоритм. Гипотеза, что это верно всегда, получило название гипотезы обвала. В [29] эта гипотеза была проверена на большом количестве примеров, а также доказана для случая, когда входные строки имеют длину не больше трех. Если гипотеза обвала верна, то жадный иерархический алгоритм в самом деле является 2-приближенным, так как он строит решение, получающееся в результате обвала удвоенного кратчайшего эйлерова решения.

Целями данной работы являются

— изучение жадной гипотезы: получение новых оценок на коэффициент приближения жадного алгоритма; анализ различных усилений и обобщений жадной гипотезы;

— изучение гипотезы обвала: доказательство или опровержение; получение оценок на коэффициент приближения жадного иерархического алгоритма; выявление связей с жадной гипотезой.

Научная новизна. В процессе работы диссертантом были получены следующие результаты.

1. Исследование иерархического графа. Результаты этого раздела опубликованы в [30]. Было предложено понятие нормализованного эйлерова решения решения, которое не изменяется при выполнении алгоритма обвала, а также показано, что нормализованные решения имеют зигзаговую форму, то есть мультимножество их ребер задают цикл вида

е ^----^ SCT(1) ^----^ ov(sCT(i), sCT(2)) ^----^ sCT(2) ^----^ sCT(n) ^----^ е

для некоторой перестановки а.

Было показано (Claim 2 и Theorem 3 в [30]), что жадное иерархическое решение является нормализованным, а соответствующая перестановка входных

строк является жадной, то есть может быть индуцирована жадным алгоритмом. Таким образом жадный иерархический алгоритм является жадным алгоритмом с некоторым правилом разрешения ничьих.

Было показано (Theorem 1 в [30]), что если обвал удвоенного эйлерова решения приводит к одному и тому же решению, то это решение с необходимостью будет жадным иерархическим. Фактически, было доказано более сильное утверждение: обвал эйлерова решения, которое содержит в себе жадное иерархическое решение, приводит к жадному иерархическому решению.

Было получено более простое доказательство утверждения, что гипотеза обвала верна для случая входных строк длины не больше трех (Theorem 6 в [30]).

2. Эквивалентность жадных алгоритмов с разными правилами разрешения ничьих. Результаты этого раздела опубликованы в [31]. Из примера на стр. 5 видно, что разные правила разрешения ничьих могут существенно влиять на результат работы жадного алгоритма, поэтому возникает естественный вопрос: отличаются ли коэффициенты приближения для алгоритмов с разными такими правилами? Было показано (Theorem 1 в [31]), что не отличаются: алгоритмы с любыми правилами разрешения ничьих имеют один и тот же коэффициент приближения. Для этого была предложена процедура возмущения, которая по данной последовательности жадных слияний изменяла входные строки таким образом, чтобы указанная последовательность стала единственной последовательностью жадных слияний, а отношение длины решения к длине оптимального было сколь угодно близко к исходному.

3. Локально жадный алгоритм. Результаты этого раздела опубликованы в [32]. Было предложено и изучено следующее усиление жадной гипотезы: надстрока, которую строит жадный алгоритм, содержит не более чем в два раза больше вхождений любого символа, чем любая другая надстрока. Мотивация такая: гипотеза обвала, грубо говоря, гласит, что есть некоторый естественный способ собрать жадную иерархическую надстроку из любой удвоенной над-строки. Значит, в частности, число вхождений любого символа в удвоенную надстроку должно быть не меньше чем в жадную иерархическую.

Это усиление интересно тем, что минимизация количества вхождений заданного символа, вообще говоря, не связана с минимизацией длины итоговой надстроки. Скажем, для набора {abn, bna} надстрока, минимизирующая число

и

вхождений а, вдвое длиннее кратчайшей, и наоборот, кратчайшая надстрока содержит в два раза больше вхождений а чем оптимальная.

В связи с этим кажется естественным предположить, что если данное усиление верно, то оно верно не только для жадного алгоритма, но и для подходящего его обобщения. В качестве такого обобщения был предложен локально жадный алгоритм, описанный ниже.

Будем говорить, что пара строк (s,t) имеет локально максимальное перекрытие, если их перекрытие имеет длину не меньше чем перекрытия как пар строк вида (s,tf)7 так и пар строк вида (sf,t). Иначе говоря, локально максимальное перекрытие является максимальным перекрытием для s справа, а для t слева.

Локально жадный алгоритм действует аналогично жадному, но на каждом шаге он сливает пару строк не с максимальным перекрытием, а с локально максимальным. Так как максимальное перекрытие является локально максимальным, жадный алгоритм является частным случаем локально жадного алгоритма.

Было обнаружено, что классическое доказательство 4-приближенности жадного алгоритма из [3] по-существу использует только четыре конкретных свойства графа перекрытий и локальную жадность жадного алгоритма, что позволило обобщить это доказательство на случай предложенного графа псевдоперекрытий абстрактного графа, который определяется этими четырьмя свойствами (Theorem 4 в [32]).

Было показано, что графы перекрытий, в которых длина строк и перекрытий определяется как количество вхождений в них некоторого символа, являются графами псевдо-перекрытий, а локально жадный алгоритм является локально жадным для всех таких графов одновременно (Theorem 1 в [32]). Таким образом локально жадная надстрока содержит не более чем в 4 раза больше вхождений произвольного символа, чем любая другая.

4. Гипотеза обвала и равномерная приближенность. Как уже обсуждалось, из гипотезы обвала следует, что в жадной над строке не может быть сильно больше вхождений некоторого символа, чем в какую-то другую. Можно ли получить обратный результат? Иначе говоря, существует ли функция качества решения такая, что ^-приближенность относительно нее была бы эквивалентна гипотезе обвала для к копий решения (в исходной гипотезе к = 2)?

В процессе работы над этим вопросом было предложено понятие равномерной ^-приближенности, основанное на предложенном понятии индуцированного вхождения.

Для строки в через я[I, г] обозначим подстроку в, которая начинается с 1-го символа и кончается г-м. Если в[£,г] = р, то [£,г] это вхождение р в в.

Рассмотрим надстроку 5 (о), соответствующую перестановке индексов а. В ней естественным образом можно выделить вхождения входных строк: с первого символа начинается вхождение строки йо-д), потом начинается вхождение строки йо(2), и так далее. Будем называть такие вхождения стандартными. Стандартное вхождение строки в й(о) обозначим через [10,г?].

Если й(о)[1,г] = р и [£,г] С [10,г0] Для иекоторого ъ, то [£,г] это вхождение р в $(о). Через ||з(о)||о обозначим чис-

ло о-иидуцироваииых вхождений р в надстроку й(о). Важно отметить, что число а-иидуцироваиных вхождений определяется именно перестановкой о, а не надстрокой 5(о) В качестве примера рассмотрим для натурального к > 1 входной набор состоящий из строк трех типов:

- I с^а ъ == 1,..., /с,

- п := Ь^d¿, ъ = 1,..., к,

- иц := а^+1-гЬг, ъ = 1,... ,к,

где с^, dj, а, Ь это попарно различные символы. Рассмотрим строку

5 = с1а^Ь^d1c2а^Ь^d2 ... скакЬкdk.

Ясно, что в это иадстрока и если мы интерпретируем ее как надстроку, соответствующую перестановке

(£1,т1,Г1,£2,т2,Г2,.. .,£к,шк,гк),

то у нее к индуцированных вхождений строки аЬ, а если как соответствующую перестановке

(11,Ш1,Ш2,.. .,тк,Г1,£2,Г2,... ,£к,гк),

то одно. Этот же пример показывает, что число индуцированных вхождений, вообще говоря, может быть меньше числа вхождений, которое для аЬ равно к.

Будем говорить, что алгоритм А построения надстроки является равномерно Х-приближенным, если для любой перестановки о и любой строки р

выполняется соотношение

где ал это перестановка, индуцированная алгоритмом.

Так как любое вхождение произвольного символа а в надстроку является также и индуцированным вхождением, то равномерно Л-приближенный алгоритм строит надстроку, число вхождений а в которую не более чем Л

Л

Л

Л

Было показано, что графы перекрытий, в которых длина строк и перекрытий определяется как количество вхождений в них некоторой строки р, являются графами псевдо-перекрытий, а локально жадный алгоритм является локально жадным для всех таких графов одновременно. Отсюда следует, что локально жадный алгоритм является равномерно 4-приближенным.

Было показано, что если обвал дизъюнктного объединения к копий любого нормализованного эйлерова решения приводит к жадному иерархическому решению, то жадный алгоритм является равномерно ^-приближенным.

Рассмотрим смелую модификацию алгоритма обвала, которая не обваливает пару (рге^й)^), (й,только в случае, если это полностью отсоединит соответствующую эйлерову компоненту от уровня |й| — 1. Показано, что из равномерной ^-приближенности жадного алгоритма следует, что смелый обвал дизъюнктного объединения к копий любого нормализованного эйлерова решения приводит к жадному иерархическому решению.

5. Нижние оценки. Под руководством диссертанта Тимофей Москаленко получил пример, на котором локально жадный алгоритм строит асимптотически в три раза более длинное решение, чем оптимальное, а Ксения Шкулева и Артем Алексеев с помощью компьютерного перебора получили пример, на котором жадный алгоритм строит решение, содержащее 5 вхождений некоторого символа, в то время как существует надстрока, содержащая 2 вхождения. Из второго примера и описанных ранее результатов следует, что гипотеза обвала неверна.

6. Простое доказательство ^-приближенности жадного алгоритма в терминах компрессии. Под руководством диссертанта Павел Калугин

р

получил более простое доказательство указанного факта, чем в работе [5], которое было упрощено автором еще сильнее и опубликовано в [33].

Теоретическая и практическая значимость. Работа носит теоретический характер. Полученные результаты и идеи могут быть использованы для дальнейшего изучения задачи о кратчайшей общей над строке.

Методология и методы исследования. В работе используются методы стрингологии, теории графов и теории приближенных алгоритмов.

Основные положения, выносимые на защиту:

1. Показано, что жадный иерархический алгоритм является частным случаем жадного алгоритма (см. Теорему 1).

2. Показано, что жадный алгоритм имеет один и тот же коэффициент (равномерного) приближения вне зависимости от правила разрешения ничьих (см. Теорему 2 и Следствие 3).

3. Предложены понятия индуцированного вхождения, равномерной А-приближепиости, локально жадного алгоритма, графа псевдоперекрытий. Обобщено доказательство 4-приближенности жадного алгоритма [3]: показано, что локально жадный алгоритм является равномерно 4-приближенным (см. Теоремы 3 и 4).

4. Показано, что если обвал дизъюнктного объединения к копий любого нормализованного эйлерова решения приводит к одному и тому же решению, то, во-первых, это решение жадное иерархическое, а во-вторых, жадный алгоритм является равномерно fc-приближенным (см. Теоремы и ). Показано, что из равномерной ^-приближенности следует, что смелый обвал к копий любого нормализованного эйлерова решения приводит к жадному иерархическому решению (см. Теорему 7).

5. Показано, что гипотеза обвала неверна (см. Следствие 7).

6. Получены простые доказательства двух утверждений: жадный алгоритм является ^-приближенным в терминах компрессии (см. Теорему 9); гипотеза обвала верна для случая строк длины не больше 3 (см. Теорему 10).

Достоверность полученных результатов обеспечивается наличием строгих математических доказательств.

Апробация работы. Основные результаты работы докладывались на:

— конференции APPROX 2019 в сентябре 2019 года в MIT;

— конференции SPIRE 2021 в октябре 2021 года онлайн;

— конференции «Проблемы теоретической информатики 2021» в декабре 2021 года в НИУ ВШЭ, Москва;

— конференции SPIRE 2024 в сентябре 2024 года, Пуэрто-Вальярта, Мексика.

Публикации. Основные результаты по теме диссертации изложены в четырех работах [30 33]. Все работы изданы в журналах, рекомендованных ВАК, и индексируемых Web of Science и Scopus.

Личный вклад. В работе [30] диссертанту принадлежат понятия нормализации решения и зигзагового решения, формулировки и первые версии доказательств Теоремы 1, Утверждения 2, Теоремы 3 и Теоремы 6. В работе [33] идея и первая версия доказательства основного результата принадлежат соавтору, окончательное короткое доказательство получено диссертантом.

Объем и структура работы. Диссертация состоит из введения, 7 глав и заключения. Полный объём диссертации составляет 69 страниц, включая 11 рисунков и 1 таблицу. Список литературы содержит 33 наименования.

Благодарности. Я невероятно благодарен своему научному руководителю Александру Сергеевичу Куликову и Ивану Михайлину за интересную задачу и многочисленные плодотворные обсуждения. Я от всего сердца благодарен своей жене за терпение и поддержку, без которых эта работа была бы невозможна.

Глава 1. Предварительные сведения

В этой части вводятся основные определения и обозначения. Для удобства изложения некоторые определения из Введения будут приведены еще раз.

1.1 Строки, перекрытия, граф перекрытий

Для строки s через |s| будем обозначать ее длину. Для нейустых строк s и ¿чере з ov(s, t) будем обозначать их перекрытие, то есть строку у наибольшей длины, такую что s = ху и t = yz для некоторых непустых строк х и г, которые мы будем обозначать через pref (s, £) и suff (s, t) соответственно. Строку xyz = pref (s, t) ov(s, t) suff (s, t) будем называть слиянием sut (см рисунок ). Через d(s,t) = | pref(s,£)| будем обозначать расстолпие между s и t. Через £ будем обозначать пустую строку.

■слияние s и t-

b | а | а | с | а b b с а а с b

■pref(s,t)-

b с а а с b а с а | а | а | ь с а

-ov(s,t)-

■suff(s,t)-

pref suff ov

На протяжение всей работы через 5 = ,..., вп} будем обозначать множество (или набор) входных строк. Будем предполагать, что никакая входная строка не является подстрокой никакой другой. В этом случае задача о над-строке сводится к задаче поиска такой перестановки индексов а : {1,... ,п} ^ {1,..., п}, что после слияния соседних строк в кортеже (йа(1),..., по-

лучается надстрока наименьшей длины. Через й(а) обозначим надстроку, получающуюся описанным выше образом из перестановки индексов а. Для

данной ст длин а й(ст) равна

^(1)! + 1 8и^ст(1),5ст(2))| + ••• + 1 ^(8ст(п — 1) , $ст(п) ) 1

= | Р^(йст(1), 5ст(2)) | + • • • + | Р^(^(п—1), «ст(п)) | + | «ст(п) | =

п— 1

= ^2 ^ 0Y(sст(г),Sст(г+1))|.

г г=1

Последнее выражение показывает, что минимизация длины надстроки эквивалентна максимизации компрессии, то есть разности между общей длиной входных строк и длиной надстроки. Это естественным образом сводит задачу о надстроке к задаче о поиске гамильтонова пути наибольшего веса в графе перекрытий ОС(Б), который является полным ориентированным графом (V, Е) с петлями, где V = Е = вес реб ра (й,£) раве н | оу(й,£)| (см. ри-

сунок 1.2).

Граф перекрытий имеет несколько ключевых свойств, часто использующихся в анализе алгоритмов для надстроки. Одно из них это неравенство треугольника:

Список литературы диссертационного исследования кандидат наук Николаев Максим Сергеевич, 2025 год

Список литературы

1. Waterman М. S. Introduction to computational biology: maps, sequences and genomes. — CRC Press, 1995.

2. Pevzner P. A., Tang #., Waterman M. S. An Eulerian path approach to DNA fragment assembly // Proceedings of the National Academy of Sciences. — 2001. — Vol. 98, no. 17. — P. 9748 9753.

3. Linear approximation of shortest superstrings / A. Blum [et al.] // Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing. — New Orleans, Louisiana, USA : Association for Computing Machinery, 1991, _ p. 328—ззб. _ (STOC '91).

4. Karpinski M.. Schmied R. Improved inapproximability results for the shortest superstring and related problems // Proceedings of the Nineteenth Computing: The Australasian Theory Symposium-Volume 141. — 2013. — P. 27—36.

5. Tarhio J., Ukkonen E. A greedy approximation algorithm for constructing shortest common superstrings // Theor. Comput. Sci. — 1988. — Vol. 57, no. 1. — P. 131—145.

6. Kaplan #., Shafrir N. The greedy algorithm for shortest superstrings // Inf. Process. Lett. — 2005. — Vol. 93, no. 1. — P. 13 17.

7. Englert M.. Matsakis N., Vesely P. Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios // Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, _ 2022. — P. 317 330.

8. Englert M.. Matsakis N., Vesely P. Approximation Guarantees for Shortest Superstrings: Simpler and Better // 34th International Symposium on Algorithms and Computation (ISAAC 2023). Vol. 283 / ed. by S. Iwata, N. Kakimura. — Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2023. — 29:1—29:17. — (Leibniz International Proceedings in Informatics (LIPIcs)).

9. Turner J. S. Approximation algorithms for the shortest common superstring problem // Inf. Comput. — 1989. — Vol. 83, no. 1. — P. 1—20.

10. Cazaux B., Rivals E. Relationship between superstring and compression measures: New insights on the greedy conjecture // Discrete Appl. Math. — 2018. — Vol. 245. — P. 59—64.

11. Kulikov A. S., Savinov S., Sluzhaev E. Greedy conjecture for strings of length 4 // CPM 2015. — Springer. 2015. — P. 307 315.

12. Gallant J., Maier D., Storer J. A. On finding minimal length superstrings // J. Comput. Syst. Sci. — 1980. — Vol. 20, no. 1. — P. 50^58.

13. Teng S.-H., Yao F. Approximating shortest superstrings // Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science. — Washington, DC, USA : IEEE Computer Society, 1993. — P. 158—165. — (SFCS'93).

14. Parallel and sequential approximation of shortest superstrings / A. Czumaj [et al.] // Algorithm Theory - SWAT'94. Vol. 824. — Springer Berlin Heidelberg, 1994. — P. 95^106. — (LNCS).

15. Kosaraju S. R., Park J. K., Stein C. Long tours and short superstrings Proceedings of the 35th Annual Symposium on Foundations of Computer Science. — Washington, DC, USA : IEEE Computer Society, 1994. — p. 106 177. — (SFCS'94).

16. Armen C., Stein C. A 2 —Approximation Algorithm for the Shortest Super-string Problem : tech. rep. / Dartmouth College. — Hanover, NH, USA, 1994.

17. Armen C., Stein C. Improved length bounds for the shortest superstring problem // Algorithms and Data Structures. Vol. 955. — Springer Berlin / Heidelberg, 1995. — P. 494 505. — (LNCS).

18. Armen C., Stein C. A 21-Approximation for the Shortest Superstring Problem // Combinatorial Pattern Matching. Vol. 1075 / ed. by D. Hirschberg, G. Myers. — Springer Berlin / Heidelberg, 1996. — P. 87—101. — (LNCS).

19. Breslauer D., Jiang T., Jiang Z. Rotations of periodic strings and short superstrings //J. Algorithms. — Duluth, MN, USA, 1997. — Aug. — Vol. 24, no. 2. — P. 340—353.

20. Sweedyk Z. 2^-Approximation Algorithm for Shortest Superstring // SIAM J. Comput. — Philadelphia, PA, USA, 1999. — Dec. — Vol. 29, no. 3. — P. 954—986.

21. Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs / H. Kaplan [et al.] // J. ACM. New York, NY, USA, 2005. July. Vol. 52, issue 4. P. 602 626.

22. Paluch Ä'., Elbassioni Ä'., Zuylen A. van. Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem // STAGS '12. Vol. 14.

2012. P. 501 506. (LIPIcs).

23. Mucha M. Lyndon Words and Short Superstrings // SODA 2013. SIAM.

2013. P. 958 972.

24. Monge G. Mémoire sur la théorie des déblais et des remblais // Histoire de l'Académie Royale des Sciences de Paris. 1781.

25. Weinard M., Schnitger G. On the greedy superstring conjecture // SIAM J. Discrete Math. 2006. Vol. 20, no. 2. P. 502 522.

26. Laube U., Weinard M. Conditional inequalities and the shortest common superstring problem // Int. J. Found. Comput. Sei. 2005. Vol. 16, no. 06. P. 1219 1230.

27. Golovnev A., Kulikov A. S., Mihajlin I. Solving SCS for bounded length strings in fewer than 2n steps // Information Processing Letters. 2014. Vol. 114, no. 8. P. 421 425.

28. De Bruijn N. G. A combinatorial problem // Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam. 1946. Vol. 49, no. 7. P. 758 764.

29. Collapsing Superstring Conjecture / A. Golovnev [et al.]. 2018. arXiv: 1809.08669vl [es.DS]. URL: https://arxiv.org/abs/1809.08669vl.

30. Collapsing Superstring Conjecture / A. Golovnev [et al.] // Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Vol. 145 / ed. by D. Achlioptas, L. A. Végh. Dagstuhl, Germany : Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019. 26:1 26:23. (Leibniz International Proceedings in Informatics (LIPIcs)). URL: https: // drops.dagstuhl.de /entities /document/10.4230/ LIPIcs. APPROX-RANDOM.2019.26.

31. Nikolaev M. S. All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent // International Symposium on String Processing and Information Retrieval. Springer. 2021. P. 61 67.

32. Nikolaev M. S. Greedy Conjecture for the Shortest Common Superstring Problem and Its Strengthenings // International Symposium on String Processing and Information Retrieval. — Springer. 2024. — P. 233—248.

33. Kalugin P. E., Nikolaev M. S. The greedy algorithm for the Shortest Common Superstring problem is a ¿-approximation in terms of compression: a simple proof // 2024 Symposium on Simplicity in Algorithms (SOSA) / ed. by M. Parter, S. Pettie. — Philadelphia, PA : Society for Industrial, Applied Mathematics, 2024. — P. 97 99.

Список рисунков

1 а) Иерархический граф для входного множества

S = {aaa, cae, aec, eee}. б) Оптимальная надстрока для S это аааесаеее. Она имеет длину 9, соответствует перестановке (aaa, aec, cae, eee), и определяет цикл длины 18, показанный черным, в) Цикл, соответствующий жадному решению ааасаесеее,

имеет длину 20............................... 8

1.1 Графическое представление понятий pref, suff и ov...........

1.2 Граф перекрытий для S = {ABE, DAB, DFA, ACB, ECA, CBD}. Тонкие ребра имеют вес ноль. Оранжевый путь это гамильтонов путь максимального веса 7, соответствующий кратчайшей надстроке DABECACBDFA, имеющей длину 6 • 3 — 7=11............... 18

1.3 Зигзаговое эйлерово решение а), соответствующее перестановке (ae, aa, ca), содержит подрешение б), соответствующее перестановке (ca, aa, ae)..........................

1.4 Этапы работы алгоритма обвала на входном наборе

{aaa, cae, aec, eee} и его оптимальном решении, а) Вначале

рассмотрим удвоенное оптимальное решение, б) После обвала всех вершин на уровне I = 3. в) После обработки вершины аа на уровне I = 2. Заметим, что алгоритм оставляет пару ребер (а, аа), (аа, а) так как они нужны, чтобы соединить эйлерову компоненту {аа, ааа} с остальным решением, г) После обработки вершины ае. Алгоритм обваливает все пары ребер этой вершины, так как она лежит в той же компоненте, что и с. д) После обработки вершины

ее. е) Наконец, после обвала всех избыточных ребер у вершин на

уровне I =1.................................

1.5 Этапы работы алгоритма обвала на входном наборе

{aaa, cae, aec, eee} и наивном решении, которое получается после слияния входных строк в том порядке, в котором они даны...... 24

1.6 Этапы работы жадного иерархического алгоритма на входном наборе {aaa, cae, aec, eee}. а) После обработки уровня I = 3. б) После обработки уровня I = 2. Заметим, что для вершины аа алгоритм добавляет два ребра (a, aa) и (aa, a), так как иначе

{ aa, aaa}

решением. В то же время алгоритм пропускает вершину ае, так как она лежит в компоненте с несбалансированными вершинами с а и ее, которые обеспечат связь соответствующей компоненты слабой связности с остальным решением, в) После обработки уровня I = 1. Заметим, что получившееся решение совпадает с решениями на рисунке 1.4е и рисунке 1.5д....................... 24

2.1 а) В эйлеровом решении вершинам = ov(sa(¡)),sa(c)) имеет пару ребер с уровня ниже, б) По этой причине v является нижней вершиной некоторой эйлеровой компоненты............... 27

3.1 а) строки Sj и Sj из б) строки s' и s'^ получающиеся после

возмущения; здесь т = 4, Та = 3, а = 1 в = 2, а = 2 и в = Та] так как а = в» = 2, мы можем заключить, что и Sj были слиты А на шаге 2.............................

4.1 Пример гамильтонова пути, построенного РАТН. В этом примере три плохих обратных ребра: (2, 2) (6,4) и (6,1), два виновника: 2

и 4 ^ 5 ^ 6 и одно слабое звено (3,4). Если удалить слабое звено, то путь распадется на два блока: 1 ^ 2 ^ 3и4 ^ 5 ^ 6 ^ 7.

2

13

центрального сегмента 4 ^ 5 ^ 6, пустого левого расширения и правого расширения 7. Таким образом, Vm = {2,4, 5,6} V¿ = {1}, Vr = {3, 7} .................................

4.2 Граф G для примера на рисунке . В верхнем ряду располагаются вершины V¿ и ребра В нижнем ряду располагаются вершины Vr и ребра Ег. Множество Е' получается добавлением к Е слабого

(3, 4)

Список таблиц

1 Известные верхние оценки на коэффициент приближения задачи о

кратчайшей общей надстроке....................... 6