Abstract for talk by Frances Rosamond

Title: Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets

The talk will survey the parameterized complexity of CLUSTER EDIT, the problem of combinatorially editing a graph so that the result is a graph consisting of disjoint cliques. The problem comes in several flavours, including: (1) where the input is an ordinary undirected graph, and the information is certain about which pairs of vertices are related (edge) and which are not (non-edge), and (2) where the input is uncertain (edge, non-edge, or “maybe”). The latter has important applications in machine learning. The talk will also survey some recent implementations of FPT algorithms for CLUSTER EDIT and results analysing large data-sets in Ecology and Medicine