2008 | OriginalPaper | Chapter
Algorithmic Graph Minors and Bidimensionality
Author : Erik D. Demaine
Published in: Parameterized and Exact Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Robertson and Seymour developed the seminal Graph Minor Theory over the past two decades. This breakthrough in graph structure theory tells us that a very wide family of graph classes (anything closed under deletion and contraction) have a rich structure similar to planar graphs. This structure has many algorithmic applications that have become increasingly prominent over the past decade. For example, Fellows and Langston showed in 1988 that it immediately leads to a wealth of (nonconstructive) fixed-parameter algorithms.
One recent approach to algorithmic graph minor theory is “bidimensionality theory”. This theory provides general tools for designing fast (constructive, often subexponential) fixed-parameter algorithms, and approximation algorithms (often PTASs), for a wide variety of NP-hard graph problems in graphs excluding a fixed minor. For example, some of the most general algorithms for feedback vertex set and connected dominating set are based on bidimensionality. Another approach is “deletion and contraction decompositions”, which split any graph excluding a fixed minor into a bounded number of small-treewidth graphs. For example, this approach has led to some of the most general algorithms for graph coloring and the Traveling Salesman Problem on graphs. I will describe these and other approaches to efficient algorithms through graph minors.