Gastvortrag: José Verschae: Searching for infections in (Un)certain Graphs: Algorithms, Complexity and Bounds

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9222

Vortragender: José Verschae

 

Abstract:

In the context of COVID-19, the methods for traceability and search for active cases played a vital role. One such method uses PCR samples in the sewage network to locate the appearance of new infections quickly.

Given a representation of the sewer network as an acyclic directed graph, we seek to design a search strategy that finds newly infected nodes while minimizing the number of samples needed in the worst case. This problem has been extensively studied in the context of perfect information, that is if the graph is known. However, in reality, we find a large amount of information missing from the network. In this talk, we will propose a model to address the problem when the network is only partially known. We will present results about the complexity of the problem, as well as tight bounds on the number of samples needed for planar graphs of bounded degrees, which is the most common case in practice. Finally, we present an optimal polynomial time algorithm for the case without uncertainty when several samples can be taken simultaneously, and finish with experimental results.