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

Ключевые слова и синонимы

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

Постановка задачи

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

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

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

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

Авторы в работе [7] сначала рассматривают существование независимых множеств вершин заданной мощности в случайных графах пересечений общего вида и приводят точные формулы для среднего значения и дисперсии числа независимых множеств вершин мощности k. Кроме того, они представляют и анализируют три алгоритма с полиномиальным временем выполнения (от числа меток m и от числа вершин n) для построения больших независимых множеств вершин в случае, когда входным значением является экземпляр модели [math]\displaystyle{ G_{n,m,p} \; }[/math]. В данной работе впервые были рассмотрены алгоритмические вопросы для этих моделей случайных графов.

Основные результаты

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

Теорема 1. Обозначим за [math]\displaystyle{ X^{(k)} }[/math] число независимых множеств размера k в случайном графе пересечений [math]\displaystyle{ G(n, m,\overrightarrow{p}) }[/math], где [math]\displaystyle{ \overrightarrow{p} = [p_1, p_2, ..., p_m] }[/math]. Тогда

[math]\displaystyle{ E \Big[ X^{(k)} \Big] = \binom{n}{k} \prod_{i=1}^m \Big( (1 - p_i)^k + kp_i (1 - p_i)^{k - 1} \Big). }[/math]

Теорема 2. Обозначим за [math]\displaystyle{ X^{(k)} }[/math] число независимых множеств размера k в случайном графе пересечений [math]\displaystyle{ G(n, m,\overrightarrow{p}) }[/math], где [math]\displaystyle{ \overrightarrow{p} = [p_1, p_2, ..., p_m] }[/math]. Тогда

[math]\displaystyle{ Var \big( X^{(k)} \big) = \sum_{s=1}^k \binom{n}{2k - s} \binom{2k - s}{s} \Big( \gamma(k, s) \frac{E[x^{(k)}]}{\binom{n}{k}} - \frac{E^2 [X^{(k)}]}{\binom{n}{k}^2} \Big) }[/math],

где [math]\displaystyle{ E[X^{(k)}] }[/math] – среднее число независимых множеств размера k,

а [math]\displaystyle{ \gamma(k, s) = \prod_{i=1}^m \Big( (1 - p_i)^{k - s} + (k - s)p_i (1 - p_i)^{k - s - 1} \Big( 1 - \frac{sp_i}{1 + (k - 1) p_i} \Big) \Big). }[/math]

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

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

Алгоритм:

Дано: случайный граф пересечений [math]\displaystyle{ G_{n,m,p} }[/math].

Требуется: найти независимое множество вершин [math]\displaystyle{ A_m }[/math].

  1.	положить [math]\displaystyle{ A_0 := V }[/math]; положить L := M;
  2.	for i: = 1 to m do
  3.	begin
  4.	   выбрать случайную метку [math]\displaystyle{ l_i \in L }[/math]; положить [math]\displaystyle{ L := L - \{ l_i \} }[/math];
  5.	   положить [math]\displaystyle{ D_i := \{ v \in A_{i - 1} : l_i \in S_v \} }[/math];
  6.	   if [math]\displaystyle{ (|D_i| \ge 1) }[/math] then выбрать случайную вершину [math]\displaystyle{ u \in D_i }[/math] и положить [math]\displaystyle{ D_i := D_i - \{ u \} }[/math];
  7.	   положить [math]\displaystyle{ A_i := A_{i - 1} - D_i }[/math];
  8.	end
  9.	output [math]\displaystyle{ A_m }[/math];

Следующая теорема рассматривает мощность независимого множества, вычисляемого алгоритмом. При анализе алгоритма используются уравнение Вальда [9] для сумм случайного количества случайных переменных, позволяющее вычислить среднее значение [math]\displaystyle{ |A_m| }[/math], и границы Чернова (см, например, [6]) для вычисления концентрации вокруг среднего значения.

Теорема 3. Для случая [math]\displaystyle{ mp = \alpha \; log \; n }[/math] для некоторой константы [math]\displaystyle{ \alpha \gt 1, m \ge n }[/math] и некоторой константы [math]\displaystyle{ \beta \gt 0 }[/math] с высокой вероятностью выполняются следующие утверждения:

1. Если [math]\displaystyle{ np \to \infty }[/math], то [math]\displaystyle{ |A_m| \ge (1 - \beta) \frac{n}{log \; n} }[/math].

2. Если [math]\displaystyle{ np \to b }[/math], где b > 0 – константа, то [math]\displaystyle{ |A_m| \ge (1 - \beta) n (1 - e^{-b}) }[/math].

3. Если [math]\displaystyle{ np \to 0 }[/math], то [math]\displaystyle{ |A_m| \ge (1 - \beta) n }[/math].

Вышеприведенная теорема доказывает, что алгоритм способен построить достаточно большое независимое множество с высокой вероятностью.

Применение

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

Во-вторых, случайные графы пересечений (и, в частности, общая модель графов пересечений из работы [7]) могут более точно моделировать задачи реального мира (по сравнению со случаем [math]\displaystyle{ G_{n,p} \; }[/math]). В частности, такие графы могут моделировать распределение ресурсов в сетях, например, когда сетевые узлы (абстрактно представленные в виде вершин) обращаются к совместно используемым ресурсам (абстрактно представленным в виде меток): в подобных задачах с распределением ресурсов граф пересечений на самом деле представляет собой граф конфликтов.

Родственные работы

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

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

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

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

Открытые вопросы

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

Конечно, многие классические задачи, касающиеся случайных графов, еще не были изучены. Одним из примеров такой задачи является размер минимального доминирующего множества (т. е. множества вершин, обладающего тем свойством, что все вершины графа либо принадлежат этому множеству, либо связаны с ним) в случайном графе пересечений. Как выглядит последовательность степеней в графах [math]\displaystyle{ G_{n,m,p} }[/math]? Эта задача радикально отличается от случая, рассмотренного в работе [11].

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

См. также

• Гамильтоновы циклы в случайных графах пересечений

Литература

1. Alon, N., Spencer, H.: The Probabilistic Method. Wiley, Inc. (2000)

2. Efthymiou, C., Spirakis, P.: On the existence of hamiltonian cycles in random intersection graphs. In: Proceedings of 32st International colloquium on Automata, Languages and Programming (ICALP), pp. 690-701. Springer, Berlin Heidelberg (2005)

3. Fill, J.A., Sheinerman, E.R., Singer-Cohen, K.B.: Random intersection graphs when m = !(n): An equivalence theorem relating the evolution of the g(n, m, p) and g(n, p) models. Random Struct. Algorithm. 16(2), 156-176 (2000)

4. Karonski, M., Scheinerman, E.R., Singer-Cohen, K.B.: On random intersection graphs: The subgraph problem. Adv. Appl. Math. 8,131-159(1999)

5. Marczewski, E.: Sur deux proprietes des classes d' ensembles. Fund. Math. 33,303-307 (1945)

6. Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press (1995)

7. Nikoletseas, S., Raptopoulos, C., Spirakis, P.: The existence and efficient construction of large independent sets in general random intersection graphs. In: Proceedings of 31st International colloquium on Automata, Languages and Programming (ICALP), pp. 1029-1040. Springer, Berlin Heidelberg (2004) Also in the Theoretical Computer Science (TCS), 2008

8. Raptopoulos, C., Spirakis, P.: Simple and efficient greedy algorithms for hamiltonian cycles in random intersection graphs. In: Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), pp 493-504. Springer, Berlin Heidelberg (2005)

9. Ross, S.: Stochastic Processes. Wiley (1995)

10. Singer-Cohen, K.B.: Random Intersection Graphs. Ph. D. thesis, John Hopkins University, Balimore (1995)

11. Stark, D.: The vertex degree distribution of random intersection graphs. Random Struct. Algorithms 24, 249-258 (2004)