Document Open Access Logo

Unconstraining Graph-Constrained Group Testing

Authors Bruce Spang, Mary Wootters

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.46.pdf
  • Filesize: 0.74 MB
  • 20 pages

Document Identifiers

Author Details

Bruce Spang
  • Stanford University, CA, USA
Mary Wootters
  • Stanford University, CA, USA

Acknowledgements

We thank Clément Canonne, Nick McKeown and the anonymous reviewers for helpful comments.

Cite As Get BibTex

Bruce Spang and Mary Wootters. Unconstraining Graph-Constrained Group Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.46

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • Group testing
  • network tomography
  • random graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Miklós Ajtai, János Komlós, and Endre Szemerédi. Largest random component of a k-cube. Combinatorica, 2(1):1-7, 1982. URL: https://doi.org/10.1007/BF02579276.
  2. Mohammad Al-Fares, Alexander Loukissas, and Amin Vahdat. A scalable, commodity data center network architecture. SIGCOMM, 2008. URL: http://dblp.org/rec/conf/sigcomm/Al-FaresLV08.
  3. Yigal Bejerano and Rajeev Rastogi. Robust Monitoring of Link Delays and Faults in IP Networks. INFOCOM, 1:134-144, 2003. URL: https://doi.org/10.1109/INFCOM.2003.1208666.
  4. Pat Bosshart, Dan Daly, Glen Gibb, Martin Izzard, Nick McKeown, Jennifer Rexford, Cole Schlesinger, Dan Talayco, Amin Vahdat, George Varghese, and David Walker. P4 - programming protocol-independent packet processors. Computer Communication Review, 44(3):87-95, 2014. URL: https://doi.org/10.1145/2656877.2656890.
  5. Rui Castro, Mark Coates, Gang Liang, Robert Nowak, and Bin Yu. Network Tomography: Recent Developments. Statistical Science, 19(3):499-517, August 2004. URL: https://doi.org/10.1214/088342304000000422.
  6. Mahdi Cheraghchi, Amin Karbasi, Soheil Mohajer, and Venkatesh Saligrama. Graph-Constrained Group Testing. CoRR, 2010. URL: http://dblp.org/rec/journals/corr/abs-1001-1445.
  7. Fan Chung and Linyuan Lu. The Volume of the Giant Component of a Random Graph with Given Expected Degrees. SIAM J. Discrete Math., 20(2):395-411, January 2006. URL: https://doi.org/10.1137/050630106.
  8. Amogh Dhamdhere, Renata Teixeira, Constantine Dovrolis, and Christophe Diot. NetDiagnoser - troubleshooting network unreachabilities using end-to-end probes and routing data. CoNEXT, page 1, 2007. URL: https://doi.org/10.1145/1364654.1364677.
  9. Michael Dinitz, Michael Schapira, and Gal Shahaf. Large low-diameter graphs are good expanders. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 71:1-71:15, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.71.
  10. Robert Dorfman. The detection of defective members of large populations. The Annals of Mathematical Statistics, 14(4):436-440, 1943. Google Scholar
  11. Ding-Zhu Du and Frank K Hwang. Combinatorial Group Testing and Its Applications, volume 12 of Series on Applied Mathematics. World Scientific Publishing Co. Pte. Ltd., 2 edition, 1999. URL: https://doi.org/10.1142/9789812798107.
  12. Nick G Duffield. Network Tomography of Binary Network Performance Characteristics. IEEE Trans. Information Theory, 2006. URL: https://dblp.org/rec/journals/tit/Duffield06.
  13. Arkadii Georgievich D'yachkov and Vladimir Vasil'evich Rykov. Bounds on the length of disjunctive codes. Problemy Peredachi Informatsii, 18(3):7-13, 1982. Google Scholar
  14. Jack Edmonds and Ellis L Johnson. Matching, Euler tours and the Chinese postman. Mathematical Programming, 5(1):88-124, 1973. URL: https://doi.org/10.1007/BF01580113.
  15. Paul Erdös and Alfréd Rényi. On random graphs I. Publicationes Mathematicae Debrecen, 6:290-298, 1959. Google Scholar
  16. Alan M Frieze, Michael Krivelevich, and Ryan R Martin. The emergence of a giant component in random subgraphs of pseudo-random graphs. Random Struct. Algorithms, 24(1):42-50, 2004. URL: https://doi.org/10.1002/rsa.10100.
  17. Charles Miller Grinstead and James Laurie Snell. Introduction to probability. American Mathematical Soc., 2012. Google Scholar
  18. Nicholas J A Harvey, Mihai Patrascu, Yonggang Wen, Sergey Yekhanin, and Vincent W S Chan. Non-Adaptive Fault Diagnosis for All-Optical Networks via Combinatorial Group Testing on Graphs. INFOCOM, pages 697-705, 2007. URL: https://doi.org/10.1109/INFCOM.2007.87.
  19. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(04):439-562, October 2006. URL: https://doi.org/10.1090/S0273-0979-06-01126-8.
  20. Amin Karbasi and Morteza Zadimoghaddam. Sequential group testing with graph constraints. In 2012 IEEE Information Theory Workshop, pages 292-296. IEEE, 2012. URL: https://doi.org/10.1109/itw.2012.6404678.
  21. David R Karger. Using Randomized Sparsification to Approximate Minimum Cuts. SODA, 1994. URL: https://dblp.org/rec/conf/soda/Karger94.
  22. Michael Krivelevich and Benny Sudakov. The phase transition in random graphs - A simple proof. Random Struct. Algorithms, 2013. URL: https://dblp.org/rec/journals/rsa/KrivelevichS13.
  23. Charles E Leiserson. Fat-trees: universal networks for hardware-efficient supercomputing. IEEE transactions on Computers, 100(10):892-901, 1985. Google Scholar
  24. Hung Xuan Nguyen and Patrick Thiran. The Boolean Solution to the Congested IP Link Location Problem - Theory and Practice. INFOCOM, pages 2117-2125, 2007. URL: https://doi.org/10.1109/INFCOM.2007.245.
  25. Ely Porat and Amir Rothschild. Explicit Non-Adaptive Combinatorial Group Testing Schemes. WINE, cs.DS, 2007. URL: http://arxiv.org/abs/0712.3876v5.
  26. Arjun Roy, Hongyi Zeng, Jasmeet Bagga, and Alex C Snoeren. Passive Realtime Datacenter Fault Detection and Localization. NSDI, 2017. URL: https://dblp.org/rec/conf/nsdi/RoyZBS17.
  27. Miklós Ruszinkó. On the Upper Bound of the Size of the r-Cover-Free Families. Journal of Combinatorial Theory, pages 302-310, 1994. URL: https://dblp.org/rec/journals/jct/Ruszinko94.
  28. Bruce Spang and Mary Wootters. Unconstraining graph-constrained group testing. arXiv preprint, 2018. URL: http://arxiv.org/abs/1809.03589.
  29. Asaf Valadarsky, Gal Shahaf, Michael Dinitz, and Michael Schapira. Xpander - Towards Optimal-Performance Datacenters. CoNEXT, 2016. URL: http://dblp.org/rec/conf/conext/ValadarskySDS16.
  30. Hongyi Zeng, Peyman Kazemian, George Varghese, and Nick McKeown. Automatic Test Packet Generation. IEEE/ACM Transactions on Networking, 22(2):554-566, April 2013. URL: https://doi.org/10.1109/TNET.2013.2253121.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact