Paper Info
Title
Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries
Abstract
Suppose that we have (i) a graph with an unknown edge set and (ii) access to an oracle that returns all neighbors of a probed vertex. We want to find the hubs, that is, vertices with degree above a given threshold. An almost obvious two-stage randomized strategy is to query randomly sampled vertices and then their neighbors. We prove that this strategy achieves, in certain classes of sparse graphs, an asymptotically optimal query number among all possible querying strategies, including adaptive strategies. A detail of importance for an optimal constant factor is the number of probes in the neighborhood of a hub candidate. We show that 2 is in general the best choice in the graphs of interest. In a similar way we analyze, in the same model, the problem of finding small, almost dominating sets. The problems and graph classes are motivated mainly by the elucidation of interaction networks in molecular biology. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(4), 344-350 2011 © 2011 Wiley Periodicals, Inc.
Year
DOI
Venue
2011
10.1002/net.20404
Networks
Keywords
Field
DocType
possible querying strategy,sparse graph,wiley periodicals,best choice,inc. networks,randomized neighborhood query,graph class,hidden hub,optimal constant factor,adaptive strategy,asymptotically optimal query number,obvious two-stage randomized strategy,sampling,degree sequence,dominating set
Discrete mathematics,Mathematical optimization,Combinatorics,Dominating set,Vertex (geometry),Oracle,Independent set,Degree (graph theory),Asymptotically optimal algorithm,Mathematics,Dense graph,Maximal independent set
Journal
Volume
Issue
ISSN
57
4
0028-3045
Citations 
PageRank 
References 
0
0.34
3
Authors
1
Name
Order
Citations
PageRank
Peter Damaschke147156.99