Введение

В теории графов метрическое измерение графа G — это минимальная мощность подмножества вершин S, такая что все остальные вершины однозначно определяются по своим расстояниям до вершин из S. Вычисление метрического измерения графа является NP-трудной задачей; задача принятия решения, определяющая, меньше ли метрическое измерение заданного значения, является NP-полной.

Подробное определение

Для упорядоченного подмножества вершин W и вершины v в связном графе G, представлением v относительно W является упорядоченный k-кортеж, где d(x,y) обозначает расстояние между вершинами x и y. Множество W является разрешающим множеством (или множеством локализации) для G, если для любых двух вершин G их представления различны. Метрическое измерение G – это минимальная мощность разрешающего множества для G. Разрешающее множество, содержащее минимальное число вершин, называется основой (или референтным множеством) для G. Разрешающие множества для графов были введены независимо и , а понятие разрешающего множества и метрического измерения были определены значительно раньше в более общем контексте метрических пространств Блюменталем в его монографии «Теория и применение геометрии расстояний». Графы являются частными примерами метрических пространств с их внутренней метрикой путей.

Деревья

Если дерево является путем, то его метрическое измерение равно одному. В противном случае, пусть L обозначает множество листьев, то есть вершин степени один в дереве. Пусть K – множество вершин, имеющих степень больше двух, которые соединены путями, состоящими из вершин степени два, с одним или несколькими листьями. Тогда метрическое измерение равно |L| – |K|. Базис такой мощности может быть сформирован путем удаления из L одного листа, связанного с каждой вершиной в K. Тот же алгоритм применим и к линейному графу дерева, и, следовательно, любое дерево и его линейный граф имеют одинаковое метрическое измерение.

Отношения между порядком, метрическим измерением и диаметром

доказать неравенство для любого графа с n вершинами, имеющего диаметр и метрическое измерение. Эти границы следуют из того факта, что каждая вершина, не входящая в разрешающее множество, однозначно определяется вектором расстояний длины, каждый элемент которого является целым числом от 1 до (существует ровно таких векторов). Однако, данная граница достигается только для или ; более точная граница доказывается для конкретных классов графов могут существовать более строгие границы. Например, доказал, что для деревьев (граница точная для четных значений D), и границу вида для внешнепланарных графов. Те же авторы доказали, что для графов, не имеющих в качестве минора полного графа порядка t, а также получили границы для хордальных графов и графов ограниченной ширины дерева. Авторы доказали границы вида для интервальных графов и пермутационных графов, а также границы вида для унитарных интервальных графов, бипартитных пермутационных графов и кографов.

Сложность решения

Решение задачи о том, не превышает ли метрическое измерение графа заданное целое число, является NP-полной. Она остаётся NP-полной для планарных графов ограниченной степени, расщеплённых графов, двудольных графов и их дополнений, линейных графов двудольных графов, графов единичных дисков, интервальных графов диаметра 2 и перестановочных графов диаметра 2, а также графов с ограниченной шириной дерева. Для любой фиксированной константы k, графы с метрическим измерением не более k могут быть распознаны за полиномиальное время, путём проверки всех возможных k-кортежей вершин, но этот алгоритм не является алгоритмом с фиксированными параметрами (для естественного параметра k, размера решения). Отвечая на вопрос, поставленный , мы показываем, что задача принятия решения о метрическом измерении является полной для параметризованного класса сложности W[2], что подразумевает, что временная сложность вида nO(k), достигнутая этим наивным алгоритмом, вероятно, является оптимальной, и что алгоритм с фиксированными параметрами (для параметризации k) вряд ли существует. Тем не менее, задача становится разрешимой с фиксированными параметрами, когда она ограничена интервальными графами и, в более общем случае, графами с ограниченной длиной дерева, такими как хордальные графы, перестановочные графы или графы, не содержащие астероидных троек. Определение, не превышает ли метрическое измерение дерева заданное целое число, может быть выполнено за линейное время. Существуют другие алгоритмы с линейной временной сложностью для кографов, цепных графов и кактусовых блок-графов (класс, включающий как кактусовые графы, так и блок-графы). Задача может быть решена за полиномиальное время для внешнепланарных графов. Она также может быть решена за полиномиальное время для графов с ограниченным цикломатическим числом, но этот алгоритм снова не является алгоритмом с фиксированными параметрами (для параметра "цикломатическое число"), поскольку показатель в полиноме зависит от цикломатического числа. Существуют алгоритмы с фиксированными параметрами для решения задачи о метрическом измерении для параметров "покрытие вершинами", "максимальное число листьев" и "модульная ширина". Графы с ограниченным цикломатическим числом, числом покрытия вершинами или максимальным числом листьев имеют ограниченную ширину дерева, однако остаётся открытой проблемой определение сложности задачи о метрическом измерении даже для графов ширины дерева 2, то есть для последовательно-параллельных графов.

Сложность приближения

Метрическое измерение произвольного графа с n вершинами может быть приближено за полиномиальное время с точностью до коэффициента приближения, представив его как задачу о покрытии множеств – задачу покрытия заданной коллекции элементов минимальным количеством множеств из заданной семьи множеств. В задаче о покрытии множеств, полученной из задачи о метрическом измерении, элементами, которые необходимо покрыть, являются пары вершин, которые требуется различить, а множествами, способными их покрыть, – множества пар, которые можно различить, выбрав одну вершину. Затем можно применить стандартные алгоритмы приближения для задачи о покрытии множеств, чтобы получить требуемое приближение. Альтернативный жадный алгоритм, выбирающий вершины на основе разницы в энтропии между классами эквивалентности векторов расстояний до и после выбора, достигает еще более высокого коэффициента приближения. Этот коэффициент приближения близок к оптимальному, поскольку при стандартных предположениях теории сложности коэффициент не может быть достигнут за полиномиальное время для любой задачи. Указанная сложность приближения сохраняется и для экземпляров, ограниченных субкубическими графами, и даже для двудольных субкубических графов.