DIKU Bits: The vertex connectivity problem

Insight, inspiration, motivation

On 14 September, Danupon Nanongkai from the Algorithms and Complexity (AC) section at Department of Computer Science, University of Copenhagen, will give a DIKU Bits lecture. 

SpeakerPortrait of Danupon Nanongkai

Danupon Nanongkai, professor in Algorithms and Complexity (AC) section, Department of Computer Science, University of Copenhagen

Title 

The vertex connectivity problem

Abstract

The vertex connectivity of a network G is the minimum number k of nodes whose removal disconnects G. Computing k=1 is a textbook exercise and requires linear time (hint: DFS). Solving k=2 also requires linear time using the SPQR tree data structure. However, for larger k we have been stuck with quadratic time from the 1950s. I will present a simple algorithm that makes the first progress in many decades and highlights a new paradigm in algorithms design called "local algorithms". 

Bio

Which courses do you teach? (BSc and MSc) I am co-teaching "Advanced algorithms and data structures" and "Topics in Algorithms and Data Structures (TADS)". I will also be co-teaching "Approximation Algorithms". 

Which technology/research/projects/startup are you excited to see the evolution of? As a person working with algorithms and complexity, I am excited with the recent tremendous progress on fundamental algorithmic questions that we have been stuck with for many decades, such as max-flow and matching, and how seemingly unrelated techniques are put together to achieve this. Beyond my own field, decades ago I was interested in making computers competent in the game of Go, so I am very impressed by how this has been achieved.

What is your favorite sketch from the DIKUrevy? I haven't watched the DIKUrevy yet.