##### Dagstuhl Seminar 13121

### Bidimensional Structures: Algorithms, Combinatorics and Logic

##### ( Mar 17 – Mar 22, 2013 )

##### Permalink

##### 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)

##### Contact

- Susanne Bach-Bernhard (for administrative matters)

##### Impacts

- Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs : article in FOCS 2014 : 2014 IEEE Annual Symposium on Foundations of Computer Science : pp. 276-285 - Pilipczuk, Marcin; Pilipczuk, Michal; Sankowski, Piotr; Leeuwen, Jan van - Los Alamitos : IEEE, 2014. - pp. 276-285 - (IEEE Annual Symposium on Foundations of Computer Science FOCS 2014).
- Network sparsification for Steiner problems on planar and bounded-genus graphs : preliminary version : Dagstuhl Seminars 13121, 13421, 14071 - Pilipczuk, Marcin; Pilipczuk, Michal; Sankowski, Piotr; van Leeuwen, Erik Jan - 2014.

##### Schedule

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.

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.

- 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]

##### Related Seminars

- Dagstuhl Seminar 11071: Theory and Applications of Graph Searching Problems (GRASTA 2011) (2011-02-13 - 2011-02-18) (Details)

##### Classification

- data structures
- algorithms
- complexity / verification
- logic

##### Keywords

- Algorithms
- Graph Minors
- Treewidth
- Grids