Задача Штейнера о минимальном дереве на графах и сетях

Введение

В комбинаторной математике проблема дерева Штайнера, или проблема минимального дерева Штайнера, названная в честь Якоба Штайнера, является общим термином для класса задач в комбинаторной оптимизации. Хотя задачи дерева Штайнера могут быть сформулированы в различных условиях, все они требуют оптимального соединения для заданного набора объектов и предопределенной целевой функции. Одним из известных вариантов, который часто используется как синоним термина «проблема дерева Штайнера», является проблема дерева Штайнера в графах. Для неориентированного графа с неотрицательными весами ребер и подмножества вершин, обычно называемых терминалами, задача дерева Штайнера в графах требует дерева минимального веса, которое содержит все терминалы (но может включать дополнительные вершины) и минимизирует общий вес его ребер. Другие известные варианты – проблема евклидова дерева Штайнера и проблема прямоугольного минимального дерева Штайнера. Проблему дерева Штайнера в графах можно рассматривать как обобщение двух других известных задач комбинаторной оптимизации: задачи (неотрицательного) кратчайшего пути и задачи минимального остовного дерева. Если задача дерева Штайнера в графах содержит ровно два терминала, она сводится к поиску кратчайшего пути. Если же, напротив, все вершины являются терминалами, то задача дерева Штайнера в графах эквивалентна задаче минимального остовного дерева. Однако, хотя и задача неотрицательного кратчайшего пути, и задача минимального остовного дерева могут быть решены за полиномиальное время, для задачи дерева Штайнера такого решения не известно. Ее вариант принятия решения, спрашивающий, существует ли для данного входного графа дерево веса меньше заданного порога, является NP-полной, что подразумевает, что вариант оптимизации, требующий найти дерево минимального веса в заданном графе, является NP-трудной. Фактически, вариант принятия решения входил в число первоначальных 21 NP-полных задач Карпа. Проблема дерева Штайнера в графах находит применение в разработке схем и проектировании сетей. Однако практические приложения обычно требуют модификаций, что приводит к множеству вариантов задачи дерева Штайнера. Большинство версий задачи дерева Штайнера являются NP-трудными, но некоторые частные случаи могут быть решены за полиномиальное время. Несмотря на пессимистичную сложность в худшем случае, несколько вариантов задачи дерева Штайнера, включая проблему дерева Штайнера в графах и проблему прямоугольного дерева Штайнера, могут быть эффективно решены на практике, даже для крупномасштабных реальных задач.

On short connecting networks with added vertices

In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices) and minimizes the total weight of its edges. Further well known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem. The Steiner tree problem in graphs can be seen as a generalization of two other famous combinatorial optimization problems: the (non negative) shortest path problem and the minimum spanning tree problem. If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding the shortest path. If, on the other hand, all vertices are terminals, the Steiner tree problem in graphs is equivalent to the minimum spanning tree. However, while both the non negative shortest path and the minimum spanning tree problem are solvable in polynomial time, no such solution is known for the Steiner tree problem. Its decision variant, asking whether a given input has a tree of weight less than some given threshold, is NP complete, which implies that the optimization variant, asking for the minimum weight tree in a given graph, is NP hard. In fact, the decision variant was among Karp's original 21 NP complete problems. The Steiner tree problem in graphs has applications in circuit layout or network design. However, practical applications usually require variations, giving rise to a multitude of Steiner tree problem variants. Most versions of the Steiner tree problem are NP hard, but some restricted cases can be solved in polynomial time. Despite the pessimistic worst case complexity, several Steiner tree problem variants, including the Steiner tree problem in graphs and the rectilinear Steiner tree problem, can be solved efficiently in practice, even for large scale real world problems.

Евклидово дерево Штайнера

Первоначальная задача была сформулирована в виде, известном как задача Евклидова дерева Штейнера или геометрическая задача о дереве Штейнера: для заданных N точек на плоскости требуется соединить их линиями минимальной общей длины таким образом, чтобы любые две точки могли быть соединены отрезками прямых либо напрямую, либо через другие точки и отрезки. Хотя задача названа в честь Штейнера, она была впервые поставлена в 1811 году Жозефом Дием Гергонном в следующей формулировке: «Несколько городов расположены в известных местах на плоскости; задача состоит в том, чтобы соединить их системой каналов минимальной общей длины». Можно показать, что соединяющие отрезки не пересекаются, за исключением конечных точек, и образуют дерево, отсюда и название задачи. Задача для N = 3 долгое время исследовалась и быстро распространилась на задачу поиска звездной сети с единственным узлом, соединяющим все N заданных точек, минимальной общей длины. Однако, хотя полная задача о дереве Штейнера была сформулирована в письме Гаусса, ее первое серьезное исследование было проведено в статье 1934 года, написанной на чешском языке Войтехом Ярником и соавторами. Эта статья долгое время оставалась незамеченной, но уже содержала «практически все общие свойства деревьев Штейнера», которые впоследствии приписывались другим исследователям, включая обобщение задачи с плоскости на более высокие размерности. Для Евклидовой задачи о дереве Штейнера точки, добавляемые к графу (точки Штейнера), должны иметь степень три, а три ребра, инцидентные такой точке, должны образовывать три угла в 120 градусов (см. точку Ферма). Следовательно, максимальное количество точек Штейнера, которое может иметь дерево Штейнера, равно N − 2, где N — начальное число заданных точек. (Все эти свойства были установлены еще Гергонном.) Для N = 3 существует два возможных случая: если треугольник, образованный заданными точками, имеет все углы, меньшие 120 градусов, решение дается точкой Штейнера, расположенной в точке Ферма; в противном случае решение дается двумя сторонами треугольника, которые сходятся в угле, равном 120 градусам или более. Для общего N задача Евклидова дерева Штейнера является NP-трудной, и поэтому неизвестно, можно ли найти оптимальное решение с помощью алгоритма полиномиального времени. Однако существует схема полиномиального приближения по времени (PTAS) для Евклидовых деревьев Штейнера, то есть решение, близкое к оптимальному, может быть найдено за полиномиальное время. Неизвестно, является ли задача Евклидова дерева Штейнера NP-полной, поскольку ее принадлежность к классу сложности NP не установлена.

The original problem was stated in the form that has become known as the Euclidean Steiner tree problem or geometric Steiner tree problem: Given N points in the plane, the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments. While the problem is named after Steiner, it has first been posed in 1811 by Joseph Diez Gergonne in the following form: "A number of cities are located at known locations on a plane; the problem is to link them together by a system of canals whose total length is as small as possible". It may be shown that the connecting line segments do not intersect each other except at the endpoints and form a tree, hence the name of the problem. The problem for N = 3 has long been considered, and quickly extended to the problem of finding a star network with a single hub connecting to all of the N given points, of minimum total length. However, although the full Steiner tree problem was formulated in a letter by Gauss, its first serious treatment was in a 1934 paper written in Czech by Vojtěch Jarník and cs. This paper was long overlooked, but it already contains "virtually all general properties of Steiner trees" later attributed to other researchers, including the generalization of the problem from the plane to higher dimensions. For the Euclidean Steiner problem, points added to the graph (Steiner points) must have a degree of three, and the three edges incident to such a point must form three 120 degree angles (see Fermat point). It follows that the maximum number of Steiner points that a Steiner tree can have is N − 2, where N is the initial number of given points. (all these properties were established already by Gergonne.) For N = 3 there are two possible cases: if the triangle formed by the given points has all angles which are less than 120 degrees, the solution is given by a Steiner point located at the Fermat point; otherwise the solution is given by the two sides of the triangle which meet on the angle with 120 or more degrees. For general N, the Euclidean Steiner tree problem is NP hard, and hence it is not known whether an optimal solution can be found by using a polynomial time algorithm. However, there is a polynomial time approximation scheme (PTAS) for Euclidean Steiner trees, i. e., a near optimal solution can be found in polynomial time. It is not known whether the Euclidean Steiner tree problem is NP complete, since membership to the complexity class NP is not known.

Прямолинейное дерево Штайнера

Проблема прямолинейного дерева Штайнера — это вариант геометрической задачи о дереве Штайнера на плоскости, в которой евклидово расстояние заменяется на манхэттенское (прямолинейное) расстояние. Эта задача возникает при физическом проектировании в автоматизированном проектировании электронных схем. В интегральных схемах (СБИС) трассировка соединений выполняется проводниками, которые часто, согласно правилам проектирования, могут прокладываться только в вертикальном и горизонтальном направлениях, поэтому задача о прямолинейном дереве Штайнера может быть использована для моделирования трассировки сетей с более чем двумя выводами.

Дерево Штайнера в графиках и вариантах

Деревья Штайнера были широко изучены в контексте взвешенных графов. Прототипом, пожалуй, является задача о дереве Штайнера в графах. Пусть G = (V, E) – неориентированный граф с неотрицательными весами ребер c, и пусть S ⊆ V – подмножество вершин, называемое терминалами. Дерево Штайнера – это дерево в G, которое охватывает S. Существует две версии задачи: в задаче оптимизации, связанной с деревьями Штайнера, требуется найти дерево Штайнера минимального веса; в задаче принятия решений веса ребер являются целыми числами, и требуется определить, существует ли дерево Штайнера, общий вес которого не превышает заданного натурального числа k. Задача принятия решений является одной из 21 NP-полных задач Карпа; следовательно, задача оптимизации является NP-трудной. Задачи о деревьях Штайнера в графах применяются к различным задачам в исследованиях и промышленности, включая маршрутизацию многоадресной рассылки и биоинформатику. Особым случаем является ситуация, когда G – полный граф, каждая вершина v ∈ V соответствует точке в метрическом пространстве, а веса ребер w(e) для каждого e ∈ E соответствуют расстояниям в этом пространстве. Иными словами, веса ребер удовлетворяют неравенству треугольника. Этот вариант известен как метрическая задача о дереве Штайнера. Для данного экземпляра (неметрической) задачи о дереве Штайнера можно в полиномиальное время преобразовать его в эквивалентный экземпляр метрической задачи о дереве Штайнера; преобразование сохраняет фактор приближения. В то время как евклидова версия допускает PTAS, известно, что метрическая задача о дереве Штайнера является APX-полной, то есть, если P = NP, невозможно достичь коэффициентов приближения, которые были бы произвольно близки к 1 за полиномиальное время. Существует алгоритм, работающий за полиномиальное время, который приближает минимальное дерево Штайнера с точностью до коэффициента ; однако, приближение с точностью до коэффициента является NP-трудным. Для частного случая задачи о дереве Штайнера с расстояниями 1 и 2 известен алгоритм приближения с точностью 1,25. Карпинский и Александр Зеликовский построили PTAS для плотных экземпляров задач о дереве Штайнера. В особом случае графовой задачи, а именно задачи о дереве Штайнера для квазидвудольных графов, требуется, чтобы S включал по крайней мере одну конечную точку каждого ребра в G.

Steiner trees have been extensively studied in the context of weighted graphs. The prototype is, arguably, the Steiner tree problem in graphs. Let G = (V, E) be an undirected graph with non negative edge weights c and let S ⊆ V be a subset of vertices, called terminals. A Steiner tree is a tree in G that spans S. There are two versions of the problem: in the optimization problem associated with Steiner trees, the task is to find a minimum weight Steiner tree; in the decision problem the edge weights are integers and the task is to determine whether a Steiner tree exists whose total weight does not exceed a predefined natural number k. The decision problem is one of Karp's 21 NP complete problems; hence the optimization problem is NP hard. Steiner tree problems in graphs are applied to various problems in research and industry, including multicast routing and bioinformatics. A special case of this problem is when G is a complete graph, each vertex v ∈ V corresponds to a point in a metric space, and the edge weights w(e) for each e ∈ E correspond to distances in the space. Put otherwise, the edge weights satisfy the triangle inequality. This variant is known as the metric Steiner tree problem. Given an instance of the (non metric) Steiner tree problem, we can transform it in polynomial time into an equivalent instance of the metric Steiner tree problem; the transformation preserves the approximation factor. While the Euclidean version admits a PTAS, it is known that the metric Steiner tree problem is APX complete, i. e., unless P = NP, it is impossible to achieve approximation ratios that are arbitrarily close to 1 in polynomial time. There is a polynomial time algorithm that approximates the minimum Steiner tree to within a factor of ;
however, approximating within a factor is NP hard. For the restricted case of Steiner Tree problem with distances 1 and 2, a 1.25 approximation algorithm is known. Karpinski and Alexander Zelikovsky constructed PTAS for the dense instances of Steiner Tree problems. In a special case of the graph problem, the Steiner tree problem for quasi bipartite graphs, S is required to include at least one endpoint of every edge in G.

Задача о дереве Штайнера также исследовалась в более высоких размерностях и на различных поверхностях. Алгоритмы для поиска дерева Штайнера минимального веса были найдены для сферы, тора, проективной плоскости, широких и узких конусов и других поверхностей. Другими обобщениями задачи о дереве Штайнера являются задача о k-реберно связанной сети Штайнера и задача о k-вершинно связанной сети Штайнера, где целью является найти k-реберно связанный граф или k-вершинно связанный граф, а не просто связанный граф. Еще одним хорошо изученным обобщением является задача проектирования отказоустойчивой сети (SNDP), где требуется соединить каждую пару вершин заданным числом (возможно, 0) реберно или вершинно непересекающихся путей. Задача Штайнера также была сформулирована в общем контексте метрических пространств и для, возможно, бесконечного числа точек.

Приближаясь к дереву Штайнера

Общая задача о дереве Штейнера для графа может быть аппроксимирована вычислением минимального остовного дерева подграфа, являющегося метрическим замыканием графа, индуцированного терминальными вершинами, впервые опубликованного в 1981 году Ку и др. Метрическое замыкание графа G – это полный граф, в котором вес каждого ребра равен кратчайшему расстоянию между узлами в G. Этот алгоритм создает дерево, вес которого не превышает вес оптимального дерева Штейнера в 2 − 2/t раз, где t – количество листьев в оптимальном дереве Штейнера; это можно доказать, рассмотрев турнейра коммивояжера по оптимальному дереву Штейнера. Это приближенное решение вычислимо за время O(|S| |V|²) путем первоначального решения задачи о кратчайших путях между всеми парами вершин для вычисления метрического замыкания, а затем решения задачи о минимальном остовном дереве. Другой популярный алгоритм для аппроксимации дерева Штейнера в графах был опубликован Такахаси и Мацуямой в 1980 году. Их решение инкрементно строит дерево Штейнера, начиная с произвольной вершины и многократно добавляя кратчайший путь от дерева к ближайшей вершине в S, которая еще не была добавлена. Этот алгоритм также имеет сложность O(|S| |V|²) и создает дерево, вес которого не превышает оптимальный вес в 2 − 2/|S| раз. В 1986 году У и др. значительно улучшили время работы, избежав предварительного вычисления кратчайших путей между всеми парами вершин. Вместо этого они используют подход, аналогичный алгоритму Крускала для вычисления минимального остовного дерева, начиная с леса из |S| несвязных деревьев и "выращивая" их одновременно, используя поиск в ширину, напоминающий алгоритм Дейкстры, но начинающийся с нескольких начальных вершин. Когда поиск находит вершину, не принадлежащую текущему дереву, два дерева объединяются в одно. Этот процесс повторяется до тех пор, пока не останется только одно дерево. Используя кучу (структуру данных) для реализации очереди с приоритетами и структуру данных непересекающихся множеств для отслеживания того, к какому дереву принадлежит каждая посещенная вершина, этот алгоритм достигает сложности O(|E| log |V|), хотя он не улучшает коэффициент 2 − 2/t, полученный Ку и др. В серии работ были представлены алгоритмы аппроксимации для задачи о минимальном дереве Штейнера с коэффициентами аппроксимации, которые улучшили соотношение 2 − 2/t. Эта последовательность завершилась алгоритмом Робинса и Зеликовского в 2000 году, который улучшил это соотношение до 1,55, итеративно улучшая минимальное остовное дерево терминальных вершин. Однако в последнее время Byrka и др. доказали аппроксимацию с использованием релаксации линейного программирования и метода, называемого итеративным рандомизированным округлением.

The general graph Steiner tree problem can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of the graph induced by the terminal vertices, as first published in 1981 by Kou et al. The metric closure of a graph G is the complete graph in which each edge is weighted by the shortest path distance between the nodes in G. This algorithm produces a tree whose weight is within a 2 − 2/t factor of the weight of the optimal Steiner tree where t is the number of leaves in the optimal Steiner tree; this can be proven by considering a traveling salesperson tour on the optimal Steiner tree. This approximate solution is computable in O(|S| |V|²) polynomial time by first solving the all pairs shortest paths problem to compute the metric closure, then by solving the minimum spanning tree problem. Another popular algorithm to approximate the Steiner tree in graphs was published by Takahashi and Matsuyama in 1980. Their solution incrementally builds up the Steiner tree by starting from an arbitrary vertex, and repeatedly adding the shortest path from the tree to the nearest vertex in S that has not yet been added. This algorithm also has O(|S| |V|²) running time, and produces a tree whose weight is within 2 − 2/|S| of optimal. In 1986, Wu et al. improved dramatically on the running time by avoiding precomputation of the all pairs shortest paths. Instead, they take a similar approach to Kruskal's algorithm for computing a minimum spanning tree, by starting from a forest of |S| disjoint trees, and "growing" them simultaneously using a breadth first search resembling Dijkstra's algorithm but starting from multiple initial vertices. When the search encounters a vertex that does not belong to the current tree, the two trees are merged into one. This process is repeated until only one tree remains. By using a Heap (data structure) to implement the priority queue and a disjoint set data structure to track to which tree each visited vertex belongs, this algorithm achieves O(|E| log |V|) running time, although it does not improve on the 2 − 2/t cost ratio from Kou et al. A series of papers provided approximation algorithms for the minimum Steiner tree problem with approximation ratios that improved upon the 2 − 2/t ratio. This sequence culminated with Robins and Zelikovsky's algorithm in 2000 which improved the ratio to 1.55 by iteratively improving upon the minimum cost terminal spanning tree. More recently, however, Byrka et al. proved an approximation using a linear programming relaxation and a technique called iterative, randomized rounding.

Параметризированная сложность дерева Штайнера

Известно, что общая задача о дереве Штейнера для графа допускает параметризованное решение с числом терминалов в качестве параметра, благодаря алгоритму Дрейфуса — Вагнера. Время работы алгоритма Дрейфуса — Вагнера составляет , где — число вершин графа, а — множество терминалов. Существуют более быстрые алгоритмы, работающие за время для любого или, в случае малых весов, за время, где — максимальный вес ребра. Недостатком вышеупомянутых алгоритмов является использование экспоненциального объёма памяти; существуют алгоритмы, требующие полиномиального объёма памяти и работающие за время и время. Известно, что для общей задачи о дереве Штейнера не существует параметризованного алгоритма, работающего за время для любого , где — число рёбер оптимального дерева Штейнера, если только задача о покрытии множества не имеет алгоритма, работающего за время для некоторого , где и — число элементов и число множеств соответственно в экземпляре задачи о покрытии множества. Более того, известно, что задача не имеет полиномиального ядра, если , даже при параметризации по числу рёбер оптимального дерева Штейнера и при условии, что все веса рёбер равны 1.

Параметризированная приближенность дерева Штайнера

В то время как задача о дереве Штейнера не имеет полиномиального ядра, если параметризация не задана числом терминалов, она допускает схему приближенного ядра полиномиального размера (PSAKS): для любого ε можно вычислить ядро полиномиального размера, которое ухудшает качество решения не более чем в ε раз. При параметризации задачи о дереве Штейнера числом нетерминалов (вершин Штейнера) в оптимальном решении, задача является W[1]-трудной (в отличие от параметризации по числу терминалов, как упоминалось выше). В то же время задача является APX-полной и, следовательно, не допускает PTAS, если P = NP. Однако существует параметризованная схема аппроксимации, которая для любого ε вычисляет ε-аппроксимацию за время f(k) * n^O(1). Для этой параметризации также существует PSAKS. Гипотеза остается открытой. Наилучшая общепринятая верхняя граница для задачи составляет 1.2134.

Для задачи о прямоугольном дереве Штейнера отношение Штейнера равно точно 1 + √2, соотношение, достигаемое четырьмя точками в квадрате с остовным деревом, использующим три стороны квадрата, и деревом Штейнера, соединяющим точки через центр квадрата. Более точно, для расстояния d квадрат должен быть наклонен под углом 45° к координатным осям, а для расстояния d квадрат должен быть выровнен по осям.