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

Существование и эффективное построение независимых множеств вершин в случайных графах пересечений

'''Определение 1 (равномерные случайные графы пересечений)'''. Рассмотрим совокупность элементов <math>M = \{1, 2, ..., m \}</math> и множество вершин <math>V = \{ v_1, v_2, ..., v_n \} </math>. Если каждой вершине <math>v_j, j = 1, 2, ..., n</math> независимым образом присвоить подмножество <math>S_{v_j}</math> множества M посредством независимого выбора каждого элемента с вероятностью p и проложить ребро между двумя вершинами <math>v_{j_1}, v_{j_2}</math> в том и только том случае, если <math>S_{v_{j_1}} \cap S_{v_{j_2}} \ne \empty </math>, то полученный граф будет представлять собой экземпляр равномерных случайных графов пересечений <math>G_{n,m,p} \;</math>.

Совокупность M иногда называется ''множеством меток'', а ее элементы – ''метками''. Обозначим за <math>L_l</math> для <math>l \in M</math> множество вершин, выбравших метку l.

В силу зависимостей от ребер эта модель способна более точно (по сравнению с моделью случайных графов Бернулли <math>G_{n,p}</math>, предполагающей независимость от ребер) абстрагировать многие практические задачи. Кроме того, Филл, Шайнерманн и Сингер-Коэн в работе [3] показали, что для некоторых диапазонов параметров <math>n, m, p (m = n^{\alpha}, \alpha > 6)</math> пространства <math>G_{n, m, p}</math> и <math>G_{n, \hat{p}}</math> являются эквивалентными в том смысле, что суммарное вариационное расстояние между переменными случайного графа имеет предел, равный 0. Николетсис, Раптопулос и Спиракис [7] предложили две новых модели, а именно модель ''случайных графов пересечений общего вида'' <math>G_{n, m,\overrightarrow{p}}, \overrightarrow{p} = [p_1, p_2, ..., p_m]</math> и модель ''регулярных случайных графов пересечений'' <math>G_{n, m, \lambda}, \lambda > 0</math>, использующих различные способы случайного присвоения меток вершинам, но применяющих одно и то же правило вхождения ребер. Модель <math>G_{n, m,\overrightarrow{p}}</math> является обобщением равномерной модели, в котором каждая метка <math>i \in M</math> выбирается независимо с вероятностью <math>p_i</math>, тогда как в модели <math>G_{n, m, \lambda}</math> каждая вершина выбирает случайное подмножество M, содержащее в точности <math>\lambda</math> меток.

Следующие теоремы рассматривают существование независимых множеств вершин мощности k в случайных графах пересечений. Доказательство теоремы 1 использует факт линейности математического ожидания суммы случайных переменных.

Теорема 1. Обозначим за X(k) число независимых множеств размера k в случайном графе пересечений <math>G_{n,m,p} \;</math>, где p = [p1; p2; pm]. Тогда m

Для доказательства теоремы 2 вначале запишем дисперсию в виде суммы ковариаций, а затем применим технику сжатия вершин, выполняющую слияние нескольких вершин в одну супер-вершину со схожим вероятностным поведением, для вычисления ковариаций. При помощи метода моментов второго порядка (см. [ 1 ]) можно вычислить порог для существования независимых множеств размера.

Один из трех предложенных в работе [ ] алгоритмов приведен далее. Алгоритм начинает работу с V (т. е. множества всех вершин графа) в качестве «кандидата» на роль независимого множества. На каждом последующем шаге он выбирает метку и удаляет из текущего кандидата на роль независимого множества все вершины, содержащие эту метку в назначенном им множестве меток, кроме одной. В силу правила вхождения ребер этот подход гарантирует, что после выполнения этой операции для всех меток множества M финальный кандидат на роль независимого множества будет содержать только вершины, не имеющие ребер между ними, и потому по определению будет являться независимым множеством.

Требуется: найти независимое множество вершин Am.

Следующая теорема рассматривает мощность независимого множества, вычисляемого алгоритмом. При анализе алгоритма используются уравнение Вальда (см. [ ]) для сумм случайного количества случайных переменных, позволяющее вычислить среднее значение jAmj, и границы Чернова (см, например, [6]) для концентрации вокруг среднего значения.

Теорема 3. Для случая mp = a log n для некоторой константы a > 1, m > n и некоторой константы ji > 0 с высокой вероятностью выполняются следующие утверждения:

2. Если np  b, где b > 0 – константа, то jAm  - e~b).

3. Если np 0 то jAmj > (1 - $)n.

Прежде всего отметим, что, как доказано в работе [ ], любой граф может быть преобразован в граф пересечений. Таким образом, модели случайных графов пересечений могут быть очень обобщенными. Кроме того, для некоторых диапазонов параметров n; m; p (m = na,a > 6) пространства <math>G_{n,m,p} \;</math> и <math>G_{n,p} \;</math> эквивалентны (что было доказано Филлом, Шайнерманом и Сингер-Коэн в работе [3], которые показали, что в этом диапазоне суммарное вариационное расстояние между переменными случайного графа имеет предел, равный 0).

В своей работе [4] Каронски и коллеги рассматривают задачу возникновения графов с константным числом вершин как порожденных подграфов графов <math>G_{n,m,p} \;</math>. Заметив, что модель <math>G_{n,m,p} \;</math> генерирует графики при помощи кликовых покрытий (например, множества Ll;l 2 M представляют собой очевидное кликовое покрытие), они вывели естественный способ их использования совместно с методами моментов первого и второго порядков для нахождения, чтобы определить пороговые значения для появления любого фиксированного графа H как порожденного подграфа <math>G_{n,m,p} \;</math> для различных значений параметров n, m и p.

Порог связности для <math>G_{n,m,p} \;</math> Карен Сингер-Коэн рассматривала в работе [10]. Она изучала случай m = na,a > 0, различая два случая в соответствии со значением a. Для случая a > 1 результаты выглядят похожими на графы <math>G_n</math>, так как среднее число ребер на порогах связности оказывается (приблизительно) одинаковым. С другой стороны, при a < 1 мы получаем более плотные графы в <math>G_{n,m,p} \;</math>. Помимо связности, в [10] также рассматривался размер наибольшей клики в равномерных случайных графах пересечений для определенных значений n, m и p.

Эфтимиу и Спиракис [ ] рассматривали существование гамильтоновых циклов в графах <math>G_{n,m,p}</math>. Используя соображения о связи, авторы показали, что порог возникновения гамильтоновых циклов достаточно близок к порогу связности <math>G_{n,m,p}</math>. Эффективные вероятностные алгоритмы нахождения гамильтоновых циклов в в равномерных случайных графах пересечений представили Раптопулос и Спиракис в работе [8]. Анализ этих алгоритмов подтверждает, что они хорошо работают с высокой вероятностью даже при значениях p, близких к порогу связности <math>G_{n,m,p}</math>. Кроме того, в той же работе предложен алгоритм нахождения гамильтоновых циклов графах в <math>G_{n,m,p}</math> с константой p с ожидаемым полиномиальным временем выполнения.

В [11] Старк представил аппроксимацию распределения степени фиксированной вершины в модели <math>G_{n,m,p}</math>. Точнее говоря, применяя метод решета, автор предлагает точную формулу для производящей функции вероятности, генерирующей степень некоторой фиксированной вершины, а затем анализирует эту формулу для различных значений параметров n, m и p.

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

Наконец, отметим, что ни один из результатов, представленных в библиографии для общих или равномерных случайных графов пересечений, нельзя сходу перенести на регулярные случайные графы пересечений. Разумеется, для некоторых значений n, m, p и A определенные свойства графов, показанные для <math>G_{n,m,p}</math>, можно доказать и для С "тд, продемонстрировав концентрацию числа меток, выбранных любой вершиной с помощью границ Чернова. Кроме того, фиксированные размеры множеств, назначенных каждой вершине, накладывают на модель дополнительные зависимости.