直径が小さいことを分散的に確認する複雑さ

グラフ$ G =(V、E)$と整数パラメータ$ k $を考えてみましょう。

私は、CONGESTモデルでは、グラフの直径が$ k
$よりもはるかに大きいか小さいかを調べるという複雑な複雑さに興味があります。

正式には、直径が最大$ k $であれば(すべての頂点)「小」を報告する必要があると仮定し、関数f $($ fなど)では$
f(k)$より大きい場合は「大」 (k)= 100k ^ 2 $)。

密接に関係する問題は、直径を近似することを要求する。この論文では、直径が最大$ 2 ell +
1であるかどうかを判断することが示されました$ 1 le ell le text {ポリロッグ}(n)$に対して、$
widetilde
Omega(n)$ラウンドが必要です。しかし、これはちょうど(小さな)定数因子近似が困難であることを示している。

アルゴリズム上の面では、$ 3/2 $近似を計算するには可能です $ O( sqrt {n log n} +
D)$ラウンド。

ラウンドの複雑さは、任意の関数$ f(k)$の$ n $に依存しますか?この依存関係が対数的に減少する$ f
$の関数がありますか?


超線形関数$ f $を許容すると、直径依存性を減らすことは可能ですか($ f ^ { – 1}(D)$など)? (例えば、$
f(k)= k ^ 2 $の場合、$ O(k ^ 2 sqrt {n}

ベストアンサー

最大$ k $のグラフと$ 2k $より大きい直径のグラフを区別するための$ O(k)$ラウンドアルゴリズムがあります。

これは2つの段階で動作します。

まず、各頂点は、$ k/2 $ラウンドについて学習した最小のIDをブロードキャストします。 頂点$ v $に対して、$ L_v
$は、この段階の最後までに$ v $が観測した最小のIDとする。

次に、アルゴリズムは$ k + 1 $を作成します。各反復で、各頂点は学習した最大の$ L_v $と最小の$ L_u
$をブロードキャストします。グラフが実際に直径$ k $の場合、すべての頂点でこれらを等しくします。

Assume that the graph has a diameter larger than $2k$, then any
vertex $v$ has a path of length at least $k+1$ starting from it.
This means that there exists a vertex $u$ such that $d(u,v)=k+1>
2(k/2)$ which implies $L_uneq L_v$. Thus, both $u,v$ would learn
that not all vertices agreed on the node with the minimal
identifier.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です