Contraction and Minor Graph Decomposition and Their Algorithmic Applications

Опубликовано 27 июля 2016, 19:31

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.