Параметризованные алгоритмы графического представления графов: различия между версиями

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

'''Теорема 4 ([9]). Если k – минимальное количество пересечений ребер в экземпляре задачи OSCM <math>(G = (V_1, V2_, E), <_1 )\;</math>, то <math>\sum_{u, v \in V_2, u \ne v} min \{ c_{uv}, v_{vu} \} \le k < 1,4664 \sum_{u, v \in V_2, u \ne v} min \{ c_{uv}, v_{vu} \} \;</math>'''.

Нагамочи предложил алгоритм аппроксимации с коэффициентом меньше 1,4664.

Далее, для любого <math>u \in V_2 \;</math> с <math>deg(u) > 0 \;</math> обозначим за <math>l_u \;</math> самого левого соседа u в <math>L_1 \;</math>, а за <math>r_u \;</math> – самого правого. Две вершины <math>u, v \in V_2 \;</math> называются неподходящими, если существует некоторое <math>x \in N(u) \;</math>, такое, что <math>l_v <_1 x <_1 r_v \;</math>, либо существует некоторое <math>x \in N(v) \;</math>, такое, что <math>l_u <_1 x <_1 r_u \;</math>. В противном случае они называются подходящими. Заметим, что для подходящих <math>{u, v} c_{uv} \cdot c_{vu} = 0 \;</math>. Джумович и Уайтсайдз показали:

Это означает, что все подходящие пары встречаются в своем естественном порядке.

Этот простой алгоритм поиска по дереву можно улучшить. Во-первых, отметим, что нет необходимости ветвления в {x, y} С V2, если cxy = cyx. Это позволяет внести две модификации в Алгоритм 1:

• На строке 5 следует исключить <math>c_{xy} = c_{yx} \;</math>.

• Как эффективно вычислить все количества пересечений cxy на этапе предварительной обработки?

'''Теорема 7. Задачу односторонней минимизации пересечений можно решить за время <math>O^*(l,4656^k) \;</math>.'''

Возможный вариант исполнения улучшенного алгоритма поиска по дереву приведен на рис. 2, а его (оптимальный) результат – на рис. 3.

1. Изменение цели оптимизации: минимизация количества дуг, участвующих в пересечениях – одноуровневая планаризация. Как было отмечено в [7, 10], из теоремы 2 практически непосредственно следует идея алгоритма решения этой задачи с временем исполнения <math>O^*(3^k) \;</math>, которое впоследствии было улучшено в [10] до <math>O^*(2^k) \;</math>.

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

 

Как и для всех алгоритмов с экспоненциальным временем исполнения, оказывается непросто улучшить это время или доказать определенную нижнюю границу времени исполнения при наличии разумных теоретико-сложностных предположений. Заметим, что негласные предположения, лежащие в основе подхода параметризованных алгоритмов, в данном сценарии полностью удовлетворяются: к примеру, графическое представление с большим количеством пересечений будет неприемлемым (если такая ситуация встретится на практике, придется прибегнуть к другому способу представления информации); таким образом, можно обоснованно предполагать, что параметр действительно окажется малым.