License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.46
URN: urn:nbn:de:0030-drops-112615
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11261/
Go to the corresponding LIPIcs Volume Portal

Spang, Bruce ; Wootters, Mary

Unconstraining Graph-Constrained Group Testing

pdf-format:
LIPIcs-APPROX-RANDOM-2019-46.pdf (0.7 MB)

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 graph-constrained group testing. Graph-constrained 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 graph-constrained group testing is near-optimal 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 connected-subgraph tests perform better not just in theory but also in practice, and in particular perform better on a real-world network topology.

BibTeX - Entry

@InProceedings{spang_et_al:LIPIcs:2019:11261,
  author =	{Bruce Spang and Mary Wootters},
  title =	{{Unconstraining Graph-Constrained Group Testing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11261},
  URN =		{urn:nbn:de:0030-drops-112615},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI