http://www.dagstuhl.de/13121

March 17 – 22 , 2013, Dagstuhl Seminar 13121

Bidimensional Structures: Algorithms, Combinatorics and Logic

Organizers

Erik D. Demaine (MIT – Cambridge, US)
Fedor V. Fomin (University of Bergen, NO)
MohammadTaghi Hajiaghayi (University of Maryland – College Park, US)
Dimitrios M. Thilikos (University of Athens, GR)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 3, Issue 3 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl's Impact: Documents available
Dagstuhl Seminar Schedule [pdf]

Summary

The monumental Graph Minors project developed by Robertson and Seymour in the 1980s is one of the most fundamental achievements of Combinatorics. The project had several groundbreaking consequences for Theoretical Computer Science. However, the wide spread opinion in the algorithmic community, expressed by David S. Johnson in his NP-Completeness Column (J. Algorithms 1987), was that it is mainly of theoretical importance. It took some time to realize that the techniques developed in Graph Minors can be used in the design of efficient and generic algorithms. One of the main techniques extracted from Graph Minors is based on the structural results explaining the existence (or the absence) of certain grid-like or bidimensional structures in graphs. The usage of bidimensional structures and the related width parameters in many areas of Computer Science and Combinatorics makes such techniques ubiquitous.

Historically, the first applications of bidimensional structures are originated in Graph Minors of Robertson and Seymour, because of the structure of the graphs excluding some fixed some graph as a minor. There is still an on-going work in Combinatorics on obtaining new structural theorems. There are much more examples in Combinatorics, where bidimensional structures and width parameters play a crucial role like in obtaining Erdös-Posa type of results. Reed used bidimensional structures to settle Erdös-Hajnal conjecture on near-bipartite graphs. Kawarabayashi and Reed used bidimensional structures to bound the size of a minimal counterexample to Hadwiger's conjecture. Demaine and Hajiaghayi optimized the original grid-exclusion theorem on H-minor free graphs.

The usage of bidimensional structures and width parameters in Algorithms goes back to the parameter of treewidth, introduced in the Graph Minors series. Treewidth is now ubiquitous in algorithm design and expresses the degree of topological resemblance of a graph to the structure of a tree. Its algorithmic importance dates back in the early 90's to the powerful meta-algorithmic result of Courcelle asserting that all graph problems expressible in Monadic Second Order Logic can be solved in linear time on graphs of bounded treewidth. Bounded treewidth can be guarantied by the exclusion of certain bidimensional structures. Intuitively, this exclusion is what enables the application of a series of classic algorithmic techniques (divide-and-conquer, dynamic programming, finite automata) for problems of certain descriptive complexity. This phenomenon was perhaps the first strong indication of the deep interleave between graph structure and logic in graph algorithms. However, a deeper understanding of it became more evident during the last decade and produced powerful meta-algorithmic techniques.

Apparently, graph-theoretic fundamentals emerging from the Graph Minors project developed by Robertson and Seymour, are used currently in several areas of Computer Science and Discrete Mathematics. Algorithmic fertilization of these ideas occurred mostly in the context of parameterized complexity and its foundational links to logic. The course of developing a structural algorithmic graph theory revealed strong connections between Graph Theory, Algorithms, Logic, and Computational Complexity and joined a rapidly developing community of researchers from Theoretical Computer Science and Discrete Mathematics.

Dagstuhl seminar 13121 brought together some of the most active researchers on this growing field.

License
  Creative Commons BY 3.0 Unported license
  Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos

Related Dagstuhl Seminar

Classification

  • Data Structures
  • Algorithms
  • Complexity / Verification
  • Logic

Keywords

  • Algorithms
  • Graph Minors
  • Treewidth
  • Grids

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.