Czas pokrycia kierowanych wykresów

17

Biorąc pod uwagę losowy spacer na wykresie, czas pokrycia jest pierwszym (oczekiwana liczba kroków), że każdy wierzchołek został trafiony (pokryty) przez spacer. W przypadku podłączonych niekierowanych wykresów czas pokrycia jest znany z górnej granicy . Istnieją silnie połączone digrafy z wykładniczym czasem pokrycia w n . Przykładem tego jest dwuznakiem składający się z kierowanego cyklu ( 1 , 2 , . . . , N , 1 ) , a krawędzie ( j , 1 ) , z wierzchołkami J = 2 , . .O(n3)n(1,2,...,n,1)(j,1)j=2,...,n1 . Począwszy od wierzchołka1 , oczekiwany czas przypadkowego przejścia do osiągnięcia wierzchołkan wynosiΩ(2n) . Mam dwa pytania :

1) Jakie są znane klasy grafów ukierunkowanych z wielomianowym czasem pokrycia? Klasy te można scharakteryzować za pomocą właściwości teoretycznych grafu (lub) właściwościami odpowiedniej macierzy sąsiedztwa (powiedzmy A ). Na przykład, jeśli A jest symetryczny, to czas pokrycia wykresu jest wielomianowy.

2) Czy istnieją prostsze przykłady (takie jak wspomniany powyżej przykład cyklu), w których czas pokrycia jest wykładniczy?

3) Czy istnieją przykłady z quasi-wielomianowym czasem pokrycia?

Byłbym wdzięczny za wszelkie wskazówki do dobrych ankiet / książek na ten temat.

Shiva Kintali
źródło
2
Twój przykład cyklu można prawdopodobnie uogólnić nieco na wykresy z ukierunkowanym obwodem z wykładniczym czasem pokrycia 2 Ω ( n / g ) . g2Ω(n/g)
Derrick Stolee
Ponadto wykresy ekspanderów najprawdopodobniej mają krótkie czasy pokrycia.
Derrick Stolee
2
W artykule Mihaila opisano, jak ograniczyć wskaźniki konwergencji zwykłych digrafów, a nawet ogólnych łańcuchów Markowa pod względem przewodności. Można go również użyć do ograniczenia czasu pokrycia (tak mi się wydaje). Patrz: ieeexplore.ieee.org/iel2/260/2317/00063529.pdf
Zeyu,
1
@Zeyu, powinna być odpowiedzią!
Suresh Venkat
1
Artykuł Fan Chung na temat „Laplacianów i nierówności Cheegera dla grafów kierowanych” jest prawdopodobnie istotny. Ma także pewne wskazówki do poprzedniej pracy Fill. springerlink.com/content/pn149711511373w9
Chandra Chekuri

Odpowiedzi:

7

Wyraźnie wielomianowy czas mieszania implikuje wielomianowy czas przykrycia. (Cóż, nie ogólnie. Potrzebujemy stacjonarnego prawdopodobieństwa co najmniej na każdym wierzchołku.) Więc sprawdź artykuł Mihaila Przewodnictwo i zbieżność łańcuchów Markowa - kombinatoryczna obróbka ekspanderów, która dowodzi szybkiego mieszania regularnego ukierunkowane wykresy i ogólne łańcuchy Markowa oparte na przewodności.1/poly(n)

Zobacz także artykuł Pseudorandom chodzi o regularne digrafy i problem RL vs. L autorstwa Reingolda, Trevisana i Vadhana. Po pracy Mihaila. Zdefiniowali parametr który jest równoważny λ 2 ( G ) , drugiej największej wartości własnej w wartości bezwzględnej, gdy wykres G jest odwracalny w czasie i pozostaje dobrze zdefiniowany dla ogólnych łańcuchów Markowa. Parametr ten jest następnie wykorzystywany do związany czasu mieszania z G .λπ(G)λ2(G)GG

Zeyu
źródło
W przypadku czasów mieszania istnieje również powiązana praca szkieletowa z wykorzystaniem tak zwanej stałej Poinare (która jest uogólnieniem luki widmowej na nieodwracalne ustawienie). Laurent Saloff Coste ma pewne uwagi ( springerlink.com/content/27114435w5149665 ) dotyczące łańcuchów Markowa w tych ramach. Istnieje również monografia ( faculty.uml.edu/rmontenegro/research/TCS008-journal.pdf ) przez Tetali i Czarnogóry. Oczywiście chodzi tu o czasy mieszania, ale może być przydatne do ograniczania czasu okładki, jak zauważył Zeyu.
Piyush,
2

Colin Cooper i Alan Frieze mają zestaw wyników w kontekście przypadkowych digrafów, które mogą być interesujące. Badają właściwości prostego losowego spaceru na losowo ukierunkowanym wykresie gdy n p = d log n , d > 1 . Udowodnili, że:Dn,pnp=dlogn,d>1

  • Dla , whp czas pokrywę D, n , p jest asymptotyczna do d log ( d / ( d - 1 ) ) n log n . Jeśli d = d ( n ) z n , czas pokrycia jest asymptotyczny do n log n .d>1Dn,pdlog(d/(d1))nlognd=d(n)nnlogn

  • Jeśli i d > 1 wówczas whp C G n , p ~ d log ( d / ( d - 1 ) ) n log n .p=dlogn/nd>1CGn,pdlog(d/(d1))nlogn

  • Niech i niech x oznaczają roztwór w ( 0 , 1 ) z x = 1 - e - d x . Niech X g będzie gigantycznym składnikiem G n , p , p = d / n . Następnie whp C X gd x ( 2 - x )d>1x(0,1)x=1edxXgGn,p,p=d/nCXgdx(2x)4(dxlogd)n(logn)2.

  • If r3 is a constant and Gn,r denotes a random r-regular graph on vertex set [n] with r3 then whp CGn,rr1r2nlogn.

  • If m2 is a constant and Gm denotes a preferential attachment graph on average degree 2m then whp CGm2mm1nlogn.

  • If k3 and Gr,k is a random geometric graph in Rk of ball size r such that the expected degree of a vertex is asymptotic to dlogn, then whp CGr,kdlog(dd1)nlogn.

See Cooper, C., & Frieze, A. Stationary distribution and cover time of random walks on random digraphs. Journal of Combinatorial Theory, Series B. (2011).

Juho
źródło