Метрическое измерение (теория графов) - Metric dimension (graph theory)

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

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

Для упорядоченного подмножества ${ displaystyle W = {w_ {1}, w_ {2}, dots, w_ {k} }}$ вершин и вершины v в связном графе грамм, представление v относительно W заказанный kпара ${ Displaystyle г (v | W) = (d (v, w_ {1}), d (v, w_ {2}), dots, d (v, w_ {k}))}$ , куда d(Икс,у) представляет собой расстояние между вершинами Икс и у. Набор W является разрешающим набором (или установочным набором) для грамм если каждые две вершины грамм имеют различные представления. Метрический размер грамм - минимальная мощность разрешающего множества для грамм. Разрешающее множество, содержащее минимальное количество вершин, называется базисом (или эталонным набором) для грамм. Разрешающие множества для графов были введены независимо Слейтер (1975) и Харари и Мелтер (1976), в то время как концепции разрешающего множества и метрической размерности были определены гораздо раньше в более общем контексте метрических пространств Блюменталь в его монографии Теория и приложения дистанционной геометрии. Графы являются частными примерами метрических пространств с их внутренней метрикой путей.

Деревья

Слейтер (1975) (смотрите также Харари и Мелтер (1976) и Хуллер, Рагхавачари и Розенфельд (1996) ) дает следующую простую характеристику метрической размерности дерево. Если дерево представляет собой путь, его метрическое измерение равно единице. В противном случае пусть L обозначают набор вершин степени один в дереве (обычно называемые листьями, хотя Слейтер использует это слово по-другому). Позволять K - множество вершин, степень которых больше двух, и которые соединены путями с вершинами степени два с одним или несколькими листами. Тогда метрическая размерность |L| − |K|, Основу этой мощности можно составить, удалив из L один из листьев, связанных с каждой вершиной в K. Тот же алгоритм действителен для линейного графа дерева, что доказано Фэн, Сюй и Ван (2013) (и, следовательно, любое дерево и его линейный график имеют одинаковую метрическую размерность).

Характеристики

В Chartrand et al. (2000), доказано, что:

Метрическое измерение графика $грамм$ равно 1 тогда и только тогда, когда $грамм$ это путь.
Метрический размер $п$ -вершинный граф $п - 1$ если и только если это полный график.
Метрический размер $п$ -вершинный граф $п - 2$ тогда и только тогда, когда граф является полный двудольный граф $K s, т$ , а разделенный график ${ displaystyle K_ {s} + { overline {K_ {t}}} (s geq 1, t geq 2)}$ , или же ${ Displaystyle K_ {s} + (K_ {1} чашка K_ {t}) (s, t geq 1)}$ .

Связь между порядком, метрическим размером и диаметром

Хуллер, Рагхавачари и Розенфельд (1996) доказать неравенство ${ Displaystyle п Leq D ^ { beta} + beta}$ для любого $п$ -вершинный граф с диаметр $D$ и метрическая размерность β. Эти границы вытекают из того факта, что каждая вершина, не входящая в разрешающий набор, однозначно определяется вектором расстояний длины β, где каждая запись является целым числом от 1 до $D$ (есть именно ${ displaystyle D ^ { beta}}$ такие векторы). Однако оценка достигается только при ${ displaystyle D leq 3}$ или же ${ displaystyle beta = 1}$ ; более точная граница ${ displaystyle n leq left ( lfloor 2D / 3 rfloor +1 right) ^ { beta} + beta sum _ {i = 1} ^ { lceil D / 3 rceil} (2i- 1) ^ { beta -1}}$ доказано Эрнандо и др. (2010).

Для определенных классов графов могут выполняться меньшие границы. Например, Beaudou et al. (2018) доказал, что ${ Displaystyle п Leq ( бета D + 4) (D + 2) / 8}$ для деревьев (граница жесткая для четных значений $D$ ), и оценка вида ${ Displaystyle п = О (D ^ {2} бета)}$ за внешнепланарные графы. Те же авторы доказали, что ${ Displaystyle п Leq (D бета +1) ^ {т-1}}$ для графиков без полный график порядка $т$ как незначительный а также дал оценки для хордовые графы и графы ограниченных ширина дерева. Авторы Foucaud et al. (2017a) доказанные оценки вида ${ Displaystyle п = О (D бета ^ {2})}$ за интервальные графики и графы перестановок, а границы вида ${ Displaystyle п = О (D бета)}$ за графики единичных интервалов, двудольные графы перестановок и кографы.

Вычислительная сложность

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

Решение о том, является ли метрическая размерность графа не более чем заданным целым числом, является NP-полным (Гэри и Джонсон 1979 ). Он остается NP-полным для ограниченной степени планарные графы (Díaz et al. 2012 г. ), разделить графики, двудольные графы и их дополняет, линейные графики двудольных графов (Эпштейн, Левин и Вегингер 2012 ), графы единичного диска (Хоффманн и Ванке 2012 ), интервальные графики диаметром 2 и графы перестановок диаметром 2 (Foucaud et al. 2017b ).

Для любой фиксированной постоянной k, графики измерения показателя не более k можно узнать в полиномиальное время, протестировав все возможные k-набор вершин, но этот алгоритм не управляемый с фиксированными параметрами (для натурального параметра k, размер решения). Отвечая на вопрос, заданный Локштанов (2010), Хартунг и Нихтерляйн (2013) показывают, что проблема решения метрической размерности является полной для параметризованного класса сложности W [2], что подразумевает, что временная граница вида п^{O (k)} достигнутый этим наивным алгоритмом, вероятно, оптимален, и что алгоритм с фиксированными параметрами (для параметризации с помощью k) вряд ли существует. Тем не менее проблема становится управляемый с фиксированными параметрами когда ограничено интервальные графики (Foucaud et al. 2017b ), и в более общем плане к графам ограниченной древовидной длины (Belmonte et al. 2015 г. ), Такие как хордовые графы, графы перестановок или графы без астероидов.

Решение о том, является ли метрическая размерность дерева не более чем заданным целым числом, может быть выполнено за линейное время (Слейтер 1975; Харари и Мельтер 1976 ). Другие алгоритмы линейного времени существуют для кографы (Эпштейн, Левин и Вегингер 2012 ), цепные графы (Fernau et al. 2015 г. ) и блочные графы кактусов (Хоффманн, Элтерман и Ванке 2016 ) (класс, включающий оба кактус графики и блочные графики ). Задача может быть решена за полиномиальное время на внешнепланарные графы (Díaz et al. 2012 г. ). Его также можно решить за полиномиальное время для графов ограниченного цикломатическое число (Эпштейн, Левин и Вегингер 2012 ), но этот алгоритм снова не является управляемым с фиксированным параметром (для параметра «цикломатическое число»), потому что показатель степени в полиноме зависит от цикломатического числа. Существуют управляемые алгоритмы с фиксированными параметрами для решения задачи измерения метрики для параметров "крышка вершины " (Hartung & Nichterlein 2013 ), «максимальное количество створок» (Эппштейн 2015 ) и «модульная ширина» (Belmonte et al. 2015 г. ). Графы с ограниченным цикломатическим числом, числом вершинных покрытий или максимальным числом листьев ограничены. ширина дерева, однако это открытая проблема - определить сложность проблемы размерности метрики даже на графах ширины дерева 2, т. е. последовательно-параллельные графы (Belmonte et al. 2015 г. ).

Сложность аппроксимации

Метрическая размерность произвольной п-вершинный граф можно аппроксимировать за полиномиальное время с точностью до коэффициент аппроксимации из ${ Displaystyle 2 журнал п}$ выразив это как установить проблему прикрытия, проблема покрытия всего заданного набора элементов как можно меньшим количеством наборов в заданном семейство наборов (Хуллер, Рагхавачари и Розенфельд, 1996 г. ). В задаче о множественном покрытии, сформированной из задачи о метрическом измерении, элементы, которые должны быть покрыты, являются ${ Displaystyle { tbinom {п} {2}}}$ пары вершин, которые должны быть выделены, и множества, которые могут покрывать их, - это множества пар, которые можно различить по одной выбранной вершине. Оценка аппроксимации затем следует путем применения стандартных алгоритмов аппроксимации для покрытия множества. Альтернатива жадный алгоритм который выбирает вершины в соответствии с разницей в энтропия между классами эквивалентности векторов расстояний до и после выбора обеспечивает еще лучший коэффициент аппроксимации, ${ Displaystyle журнал п + журнал журнал _ {2} п + 1}$ (Hauptmann, Schmied & Viehmann, 2012 г. ). Этот коэффициент аппроксимации близок к наилучшему возможному, так как при стандартных предположениях теории сложности соотношение ${ Displaystyle (1- epsilon) журнал п}$ не может быть достигнуто за полиномиальное время ни для каких ${ displaystyle epsilon> 0}$ (Hauptmann, Schmied & Viehmann, 2012 г. ). Последняя трудность приближения все еще сохраняется для случаев, ограниченных субкубическими графами (Hartung & Nichterlein 2013 ) и даже двудольный субкубические графы, как показано в докторской диссертации Хартунга (Хартунг 2014 ).