TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 13121

Bidimensional Structures: Algorithms, Combinatorics and Logic

( Mar 17 – Mar 22, 2013 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/13121

Organizers

Contact



Schedule

Motivation

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. The objective of the proposed Dagstuhl seminar is to bring together the most active researchers on this growing field and fully develop its potential.


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.

Copyright Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos

Participants
  • Isolde Adler (Goethe-Universität - Frankfurt a. M., DE) [dblp]
  • Hans L. Bodlaender (Utrecht University, NL) [dblp]
  • Paul Bonsma (University of Twente, NL) [dblp]
  • Jianer Chen (CSU-Changsha, CN) [dblp]
  • Rajesh Hemant Chitnis (University of Maryland - College Park, US) [dblp]
  • Marek Cygan (University of Warsaw, PL) [dblp]
  • Victor Dalmau (UPF - Barcelona, ES) [dblp]
  • Anuj Dawar (University of Cambridge, GB) [dblp]
  • Erik D. Demaine (MIT - Cambridge, US) [dblp]
  • Reinhard Diestel (Universität Hamburg, DE) [dblp]
  • Frederic Dorn (SINTEF - Trondheim, NO) [dblp]
  • Fedor V. Fomin (University of Bergen, NO) [dblp]
  • Archontia C. Giannopoulou (University of Bergen, NO) [dblp]
  • Petr A. Golovach (University of Bergen, NO) [dblp]
  • Alexander Grigoriev (Maastricht University, NL) [dblp]
  • MohammadTaghi Hajiaghayi (University of Maryland - College Park, US) [dblp]
  • Illya V. Hicks (Rice University - Houston, US) [dblp]
  • Gwenaël Joret (Free University of Brussels, BE) [dblp]
  • Marcin Kaminski (Free University of Brussels, BE) [dblp]
  • Iyad A. Kanj (DePaul University - Chicago, US) [dblp]
  • Mamadou Moustapha Kanté (University Blaise Pascal - Aubiere, FR) [dblp]
  • Yusuke Kobayashi (University of Tokyo, JP) [dblp]
  • Sudeshna Kolay (The Institute of Mathematical Sciences, IN) [dblp]
  • Guy Kortsarz (Rutgers University - Camden, US) [dblp]
  • Stephan Kreutzer (TU Berlin, DE) [dblp]
  • O-joung Kwon (KAIST - Daejeon, KR) [dblp]
  • Daniel Lokshtanov (University of Bergen, NO) [dblp]
  • Johann A. Makowsky (Technion - Haifa, IL) [dblp]
  • Dániel Marx (Hungarian Academy of Sciences - Budapest, HU) [dblp]
  • Frédéric Mazoit (University of Bordeaux, FR) [dblp]
  • Bojan Mohar (Simon Fraser University - Burnaby, CA) [dblp]
  • Sang-il Oum (KAIST - Daejeon, KR) [dblp]
  • Geevarghese Philip (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Marcin Pilipczuk (University of Warsaw, PL) [dblp]
  • Michal Pilipczuk (University of Bergen, NO) [dblp]
  • Felix Reidl (RWTH Aachen, DE) [dblp]
  • Peter Rossmanith (RWTH Aachen, DE) [dblp]
  • Ignasi Sau Valls (University of Montpellier 2, FR) [dblp]
  • Saket Saurabh (The Institute of Mathematical Sciences, IN) [dblp]
  • Konstantinos Stavropoulos (HU Berlin, DE) [dblp]
  • Blair D. Sullivan (Oak Ridge National Laboratory, US) [dblp]
  • Hisao Tamaki (Meiji University - Kawasaki, JP) [dblp]
  • Jan Arne Telle (University of Bergen, NO) [dblp]
  • Dimitrios M. Thilikos (University of Athens, GR) [dblp]
  • Ioan Todinca (University of Orleans, FR) [dblp]
  • Erik Jan van Leeuwen (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Yngve Villanger (University of Bergen, NO) [dblp]
  • Paul Wollan (Sapienza University of Rome, IT) [dblp]
  • Christian Wulff-Nilsen (University of Copenhagen, DK) [dblp]

Classification
  • data structures
  • algorithms
  • complexity / verification
  • logic

Keywords
  • Algorithms
  • Graph Minors
  • Treewidth
  • Grids