Theory and Applications of Bidimensionality

Dimitrios M. Thilikos 1, 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Bidimensionality Theory is a meta-algorithmic theory whose main ingredients are the Grid Exclusion Theorem of the Graph Minors series of Robertson and Seymour and the celebrated Courcelle’s Theorem. The grid exclusion theorem states that if a graph excludes a bidimensional grid as a minor (a graph H is a minor of a graph G if H can be obtained by some subgraph of G by con- tracting edges) then its structure topologically resembles the structure of a tree (in technical terms, it has small treewidth). Intuitively, this result says that the absence of the bidimensional structure of a grid implies that a graph has the “mono-dimensional” structure of a tree. On the other side, Courcelle’s theorem states that if a problem on graphs is expressible in Monadic Second Order Logic (MSOL), then it is possible to solve it in linear time when the treewidth of their input graphs is fixed. Intuitively, this theorem expresses the fact that the mono- dimensional structure of a tree (i.e., small treewidth) makes it possible to treat a graph as the input string of a finite-state tree automaton, where the finiteness of its states is guaranteed by the MSOL-expressibility of the problem. Combin- ing these two results together, we derive that the absence of the bidimensional structure of a grid, enables the applicability of the “divide-and-conquer” tech- nique for problems of certain descriptive complexity. It appears that for many graph theoretic problems the existence of a grid-minor (or other bidimensional strucures) on the input graph provides a certificate for an immediate negative (or positive) answer and, for the remaining instances, a dynamic programming approach on graphs of bounded treewidth may give an answer to the problem. This phenomenon reveals fruitful interleave between graph structure and logic in graph algorithms. Bidimensionality Theory aims at systematizing this idea and extending its applicability in diverse paradigms of algorithm design.
Type de document :
Communication dans un congrès
COCOA: Conference on Combinatorial Optimization and Applications, Dec 2013, Chengdu, China. 7th Annual International Conference on Combinatorial Optimization and Applications, 2013, Invited Lectures. 〈10.1007/978-3-319-03780-6〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01483650
Contributeur : Dimitrios M. Thilikos <>
Soumis le : vendredi 10 novembre 2017 - 09:15:50
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Fichier

taob.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Dimitrios M. Thilikos. Theory and Applications of Bidimensionality. COCOA: Conference on Combinatorial Optimization and Applications, Dec 2013, Chengdu, China. 7th Annual International Conference on Combinatorial Optimization and Applications, 2013, Invited Lectures. 〈10.1007/978-3-319-03780-6〉. 〈lirmm-01483650〉

Partager

Métriques

Consultations de la notice

14

Téléchargements de fichiers

6