Finding paths in sparse random graphs requires many queries
Finding paths in sparse random graphs requires many queries
复制标题
在稀疏随机图中查找路径需要许多查询
DOI：
10.1002/rsa.20680
复制
发表时间：
2015
影响因子：
1
通讯作者：
Pedro Vieira
中科院分区：
文献类型：
--
作者：
Asaf Ferber;Michael Krivelevich;B. Sudakov;Pedro Vieira
我们讨论了一个新的算法类型的问题，在随机图研究的最小数量的查询，一个必须问的顶点对之间的邻接的随机图G <$G（n，p），以找到一个子图，具有一些目标属性的概率高。本文主要研究当p=1+εn，ε>0时，G <$G（n，p）中的长路问题.已知该随机图具有典型的线性长路径。要在G <$G（n，p）中有高概率的边，显然需要查询至少Ω（<$p）对顶点。我们能找到一条经济上有长度的路径吗，通过查询大概这么多对？我们认为，这是不可能的，需要查询显着更多的对。证明了在G <$G（n，p）（p=1+εn）中以至少常数概率找到一条长度为<$p =Ω（log（1ε）ε）的路的随机算法必须至少查询Ω（<$pεlog（1ε））对顶点.这是紧到log（1ε）因子。© 2016 Wiley Periodicals，Inc.随机结构算法，50、71-85，2017年
We discuss a new algorithmic type of problem in random graphs studying the minimum number of queries one has to ask about adjacency between pairs of vertices of a random graph G∼G(n,p) in order to find a subgraph which possesses some target property with high probability. In this paper we focus on finding long paths in G∼G(n,p) when p=1+εn for some fixed constant ε>0 . This random graph is known to have typically linearly long paths. To have ℓ edges with high probability in G∼G(n,p) one clearly needs to query at least Ω(ℓp) pairs of vertices. Can we find a path of length ℓ economically, i.e., by querying roughly that many pairs? We argue that this is not possible and one needs to query significantly more pairs. We prove that any randomised algorithm which finds a path of length ℓ=Ω(log(1ε)ε) with at least constant probability in G∼G(n,p) with p=1+εn must query at least Ω(ℓpεlog(1ε)) pairs of vertices. This is tight up to the log(1ε) factor. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 71–85, 2017