Czas pokrycia kierowanych wykresów

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(n^3)$$n$$(1, 2, ..., n, 1)$$(j, 1)$$j = 2, ..., n − 1$ . Począwszy od wierzchołka$1$ , oczekiwany czas przypadkowego przejścia do osiągnięcia wierzchołka$n$ wynosi$\Omega(2^n)$ . 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.

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 .$\lambda_\pi(G)$$\lambda_2(G)$$G$$G$

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:$D_{n,p}$$np=d \log n, 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 > 1$$D_{n,p}$$d \log (d/(d-1)) n \log n$$d=d(n) \rightarrow \infty$$n$$n \log n$

• Jeśli i d > 1 wówczas whp C G n , p ~ d log ( d / ( d - 1 ) ) n log n .$p = d \log n/n$$d>1$$C_{G_{n,p}} \sim d \log (d/(d-1)) n \log n$

• 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 g ∼ d x ( 2 - x $d>1$$x$$(0,1)$$x = 1-e^{-dx}$$X_g$$G_{n,p},p=d/n$$C_{X_g} \sim \dfrac{dx(2-x)}{4(dx-\log d)} n (\log n)^2$.

• If $r \geq 3$ is a constant and $G_{n,r}$ denotes a random $r$-regular graph on vertex set $[n]$ with $r \geq 3$ then whp $C_{G_{n,r}} \sim \dfrac{r-1}{r-2} n \log n$.

• If $m \geq 2$ is a constant and $G_m$ denotes a preferential attachment graph on average degree $2m$ then whp $C_{G_m} \sim \dfrac{2m}{m-1} n \log n$.

• If $k \geq 3$ and $G_{r,k}$ is a random geometric graph in $\mathcal{R}^k$ of ball size $r$ such that the expected degree of a vertex is asymptotic to $d \log n$, then whp $C_{G_{r,k}} \sim d \log ( \dfrac{d}{d-1}) n \log n$.

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