Время покрытия ориентированных графов

17

При случайном блуждании на графике время покрытия - это первый раз (ожидаемое количество шагов), когда каждая вершина была поражена (покрыта) блужданием. Известно, что для связных неориентированных графов время накрытия ограничено сверху . Существуют сильно связанные орграфы с показателем времени покрытия по . Примером этого является орграф, состоящий из направленного цикла и ребер из вершин . Начиная с вершины , ожидаемое время случайного блуждания для достижения вершины равно . У меня есть два вопроса:п ( 1 , 2 , . . . , П , 1 ) ( J , 1 ) J = 2 , . , , , n - 1 1 n Ω ( 2 n )O(n3)n(1,2,...,n,1)(j,1)j=2,...,n11nΩ(2n)

1) Каковы известные классы ориентированных графов с полиномиальным накрытием времени? Эти классы могут характеризоваться теоретико-графическими свойствами (или) свойствами соответствующей матрицы смежности (скажем, ). Например, если симметрична, то время покрытия графа является полиномиальным.AAA

2) Существуют ли более простые примеры (такие как пример цикла, упомянутый выше), где время покрытия экспоненциально?

3) Есть ли примеры с квазиполиномиальным временем покрытия?

Буду признателен за любые ссылки на хорошие обзоры / книги по этой теме.

Шива Кинтали
источник
2
Ваш пример цикла, вероятно, можно немного обобщить для графиков с направленным обхватом с экспоненциальным временем покрытия . 2 Ом ( н / г )g2Ω(n/g)
Деррик Столи
Кроме того, графики расширителей, скорее всего, имеют быстрое время покрытия.
Деррик Столи
2
В статье Михаила описано, как ограничить скорости сходимости регулярных орграфов и даже общих цепей Маркова по проводимости. Это может также использоваться, чтобы связать время покрытия (я предполагаю). См .: ieeexplore.ieee.org/iel2/260/2317/00063529.pdf
Зейю
1
@Zeyu, должен быть ответ!
Суреш Венкат
1
Статья Фана Чунга «Лапласианы и неравенство Чигера для ориентированных графов», вероятно, актуальна. Он также имеет несколько указателей на предыдущую работу Fill. springerlink.com/content/pn149711511373w9
Чандра Чекури

Ответы:

7

Ясно, что полиномиальное время смешивания подразумевает полиномиальное время покрытия. (Ну, не в общем. Нам нужна стационарная вероятность, по крайней мере, в каждой вершине.) Так что проверьте статью Михаила Кондуктивность и сходимость цепей Маркова - комбинаторная обработка расширителей, которая доказывает быстрое смешивание регулярных ориентированных графов и общие цепи Маркова на основе проводимости.1/poly(n)

Также см. Статью «Псевдослучайные прогулки по регулярным орграфам и проблема RL против L » Рейнгольда, Тревизана и Вадхана. После работы Михаила. Они определили параметр который эквивалентен , второму по величине собственному значению по абсолютной величине, когда граф обратим во времени и остается хорошо определенным для общих цепей Маркова. Этот параметр затем используется для связанного времени перемешивания в .λ 2 ( G ) G Gλπ(G)λ2(G)граммграмм

Zeyu
источник
Для времен смешивания существует также связанная с этим каркасная работа, использующая так называемую постоянную Пуанкаре (которая является обобщением спектральной щели до необратимой установки). У Лорана Салоффа Коста есть несколько заметок ( springerlink.com/content/27114435w5149665 ), посвященных цепям Маркова в этой структуре. Есть также монография ( faculty.uml.edu/rmontenegro/research/TCS008-journal.pdf ) Тетали и Черногории. Конечно, речь идет о времени смешивания, но может быть полезно для ограничения времени покрытия, как указал Зейю.
Пиюш
2

Колин Купер и Алан Фриз имеют ряд результатов в контексте случайных орграфов, которые могут представлять интерес. Они изучают свойства простого случайного блуждания по случайному ориентированному графу когда . Они доказали, что: n p = d log n , d > 1Dn,pNпзнак равноdжурналN,d>1

  • При время покрытия асимптотически равно . Если с , время покрытия асимптотически равно .D n , p d log ( d / ( d - 1 ) ) n log n d = d ( n ) n n log nd>1DN,пdжурнал(d/(d-1))NжурналNdзнак равноd(N)NNжурналN

  • Если и то whp .д > 1 С С п , р ~ д лог ( д / ( д - 1 ) ) п войти ппзнак равноdжурналN/Nd>1СграммN,п~dжурнал(d/(d-1))NжурналN

  • Пусть и пусть обозначает решение в из . Пусть - гигантская компонента . Тогда whp .х ( 0 , 1 ) х = 1 - е - д х Х г О п , р , р = д / п С Й г ~ д х ( 2 - х )d>1Икс(0,1)Иксзнак равно1-е-dИксИксграммграммN,п,пзнак равноd/NСИксграмм~dИкс(2-Икс)4(dИкс-журналd)N(журналN)2

  • Если является константой, а обозначает случайный регулярный граф на множестве вершин с то whp .G n , r r [ n ] r 3 C G n , rr - 1р3граммN,рр[N]р3СграммN,р~р-1р-2NжурналN

  • Если является константой, а обозначает граф предпочтительного вложения в среднем степени то whp .G м 2 м С С м ~ 2 мм2граммм2мСграммм~2мм-1NжурналN

  • Если и - случайный геометрический граф в размера шара, такой, что ожидаемая степень вершины асимптотична , то whp .G r , k R k r d log n C G r , kd log ( dК3граммр,КрКрdжурналNСграммр,К~dжурнал(dd-1)NжурналN

См. Купер, С. & Фриз, А. Стационарное распределение и время случайных блужданий на случайных орграфах. Журнал комбинаторной теории, Серия B. (2011).

Юхо
источник