Searching infected nodes in uncertain graphs.

Abstract: In the context of the COVID-19, the development of methods to trace the spread of the virus is of vital importance. One of such methods relies on PCR testing of wastewater samples to locate sudden the appearance of infection. Given a representation of the wastewater network as a directed graph, we aim for a strategy that finds a new infected node using the worst-case minimum number of tests. This problem proves to be challenging on networks with uncertainty, as is the case of real-world data. We will explore the connection with other known graph problems and show upper bounds for the number of tests in an optimal strategy on graphs of bounded treewidth and planar graphs. Then we analyze experimental results obtained using a greedy algorithm to select nodes to sample, and finally conclude by stating several relevant open questions.

Posted on May 30, 2022 in ACGO, Seminars