Contraction and Minor Graph Decomposition and Their Algorithmic Applications

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.

Speaker Details

Dr. Mohammad T. Hajiaghayi is the Jack and Rita G. Minker Associate Professor of Computer Science at the University of Maryland with a joint appointment in the University’s Institute for Advanced Computer Studies (UMIACS). In addition, he holds a Research Affiliate position in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) and is a Permanent Member of Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers. Before joining the University of Maryland, he was a Senior Researcher in the Algorithms and Theoretical Computer Science group at AT&T Labs– Research to which he is still a consultant. Before that, he was a one-year Postdoctoral Fellow in the School of Computer Science at Carnegie Mellon University (with ALADDIN project) and a one-year Postdoctoral Associate in MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) from which he also earned his Ph.D in 2005. During his Ph.D. studies, he spent some time at IBM Research centers and Microsoft Research centers. Dr. Hajiaghayi got his M.Sc. in Computer Science from the University of Waterloo in 2001 and his B.Sc. in Computer Engineering from Sharif University of Technology in 2000.

Dr. Hajiaghayi’s research interests are algorithmic game theory and combinatorial auctions, network design, combinatorial optimizations and approximation algorithms, fixed-parameter algorithms, algorithmic graph theory, distributed and mobile computing, and computational geometry and embeddings. In the course of his professional career in these areas, he has published more than 110 papers in top conferences and journals of computer science, won a few best paper awards, and served in program committees or editorial boards of several well-known international conferences and journals. He has received an NSF CAREER Award in 2010, a Google Faculty Research Award in 2010, an ONR Young Investigator Award in 2011, and the University of Maryland Research and Scholarship Award (RASA) in 2011. He won best paper awards at the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) 2010, the International Symposium on Algorithms and Computation (ISAAC) 2006, and the Robocup 2001 Conference.