Abstract
In network tomography, one goal is to identify a small set of failed links in a network using as little information as possible. One way of setting up this problem is called graphconstrained group testing. Graphconstrained group testing is a variant of the classical combinatorial group testing problem, where the tests that one is allowed are additionally constrained by a graph. In this case, the graph is given by the underlying network topology.
The main contribution of this work is to show that for most graphs, the constraints imposed by the graph are no constraint at all. That is, the number of tests required to identify the failed links in graphconstrained group testing is nearoptimal even for the corresponding group testing problem with no graph constraints. Our approach is based on a simple randomized construction of tests. To analyze our construction, we prove new results about the size of giant components in randomly sparsified graphs.
Finally, we provide empirical results which suggest that our connectedsubgraph tests perform better not just in theory but also in practice, and in particular perform better on a realworld network topology.
BibTeX  Entry
@InProceedings{spang_et_al:LIPIcs:2019:11261,
author = {Bruce Spang and Mary Wootters},
title = {{Unconstraining GraphConstrained Group Testing}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {46:146:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11261},
URN = {urn:nbn:de:0030drops112615},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.46},
annote = {Keywords: Group testing, network tomography, random graphs}
}
Keywords: 

Group testing, network tomography, random graphs 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) 
Issue Date: 

2019 
Date of publication: 

17.09.2019 