Parameterized Preprocessing for Network Analysis Problems

Summary Many network analysis problems require a lot of resources (time and memory) to be solved. One way to speed up the computation for such problems is to employ an efficient preprocessing phase, in which one attempts to reduce the size of the problem without changing the answer. The reduced, smaller network can be analyzed more efficiently. The project aims to investigate new ways for preprocessing network analysis problems, using the framework of parameterized complexity theory and the concept of kernelization. For example, we explore which network problems can be efficiently split up into provably small pieces, such that answers to the individual pieces can efficiently be combined into an answer for the original problem. This allows the work on a network analysis problem to be divided efficiently among many nodes of a computing cluster. The existence of these so-called Turing kernelization algorithms is explored for graph-theoretical problems such as finding patterns in networks
Supervisors Mark de Berg (TU/e), Bart Jansen (TU/e)
PhD Student Astrid Pieterse
Eindhoven University of Technology (TU/e)