The covert set-cover problem with application to network discovery

DOI10.1007/978-3-642-11440-3_21MaRDI QIDQ3404448zbMATH OpenOpenAlexFDO

Authors V. N. Muralidhara, Sandeep Sen

Publication date 9 February 2010

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.1090

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We address a version of the set-cover problem where we do not know the sets initially (and hence referred to as covert) but we can query an element to find out which sets contain this element as well as query a set to know the elements. We want to find a small set-cover using a minimal number of such queries. We present a Monte Carlo randomized algorithm that approximates an optimal set-cover of size $OPT$ within $O(logN)$ factor with high probability using $O(OPTcdotlo{g}^{2}N)$ queries where $N$ is the input size. We apply this technique to the network discovery problem that involves certifying all the edges and non-edges of an unknown $n$-vertices graph based on layered-graph queries from a minimal number of vertices. By reducing it to the covert set-cover problem we present an $O(lo{g}^{2}n)$-competitive Monte Carlo randomized algorithm for the covert version of network discovery problem. The previously best known algorithm has a competitive ratio of $Omega(sqrtnlogn)$ and therefore our result achieves an exponential improvement.

Recommendations

• Set cover in sub-linear time
• Graph-Theoretic Concepts in Computer Science
• Network Discovery and Verification with Distance Queries
• The online set cover problem
• The online set cover problem

Cited in

(4)

• Algorithms that access the input via queries
• A story of diameter, radius, and (almost) Helly property
• Finding hidden independent sets in interval graphs
• Network verification via routing table queries

This page was built for publication: The covert set-cover problem with application to network discovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3404448)