Dr. Falk Hüffner (TU Berlin)

Removing as few edges as possible from a graph such that the resulting graph consists of highly connected components is a natural problem in graph-based data clustering. Building on work by Hartuv and Shamir [Inf. Proc. Lett. 2000], we introduce the corresponding combinatorial optimization problem Highly Connected Deletion, show it to be NP-hard even on 4-regular graphs, provide fixed-parameter tractability results, and describe ILP models for the problem. We demonstrate that these exact solution methods (employing data reduction techniques as well as ILP solving) provide biologically meaningful results, being able to solve real-world PPI networks with up to 5 000 vertices and 12 000 edges. Compared to the method by Hartuv and Shamir, our exact approaches find more biologically interesting structures; Hartuv and Shamir's algorithm combined with our data reduction provides a good compromise between running time and solution quality.

Back to the research colloquium site.