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.
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01483650
Contributor : Dimitrios M. Thilikos <>
Submitted on : Friday, November 10, 2017 - 9:15:50 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on : Sunday, February 11, 2018 - 1:18:38 PM

File

taob.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Dimitrios M. Thilikos. Theory and Applications of Bidimensionality. COCOA: Conference on Combinatorial Optimization and Applications, Dec 2013, Chengdu, China. ⟨10.1007/978-3-319-03780-6⟩. ⟨lirmm-01483650⟩

Share

Metrics

Record views

259

Files downloads

24