Contraction and Minor Graph Decomposition and Their Algorithmic Applications

Speaker  MohammadTaghi Hajiaghayi

Affiliation  University of Maryland

Host  Mohit Singh

Duration  01:03:32

Date recorded  26 November 2013

As a powerful new result we present a new technique to split the edges or vertices of any graph into k pieces such that contracting or deleting any piece results in a graph of bounded treewidth. The contraction result is specially interesting since many problems are closed under contraction but not deletions, suggesting that we develop a Graph Contraction Theory to parallel Graph Minor Theory. The above approach has led to the best approximation algorithms and fixed parameter algorithms for several problems such Traveling Salesman Problem, Graph Coloring, k-cut, bisection, etc on graphs excluding a fixed minor (such as planar graphs and bounded genus graphs) and their generalization. I will discuss several simple algorithms which are the best known algorithms for the above problems.

©2013 Microsoft Corporation. All rights reserved.
> Contraction and Minor Graph Decomposition and Their Algorithmic Applications