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:
##### Seminars
###### External resources:
• DOOR (for registering your stay at Dagstuhl)
• DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
##### dblp
###### External resources:
• the dblp Computer Science Bibliography

### Vertex Partitioning in Graphs: From Structure to Algorithms

##### Organizers
• (Princeton University, US)
• (Indian Institute of Techology - Madras, IN)
• (Durham University, GB)
• Oliver Schaudt (Bayer AG - Leverkusen, DE)

##### Dagstuhl Reports

As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.

##### Motivation

Many important discrete optimization problems can be modelled as graph problems that ask if the set of vertices in a graph can be partitioned into a smallest number of sets, such that each set has the same property, or into some number of sets, such that each set has a specific property of their own. This leads to a rich framework of vertex partitioning problems, which include classical problems such as Graph Colouring, Graph Homomorphism, Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal, and variants and generalizations of these problems, such as List Colouring, Connected Vertex Cover, Independent Feedback Vertex Set, and Subset Odd Cycle Transversal.

Most of these vertex partitioning problems are NP-hard. However, this situation may change if we insist that the input graph belongs to some special graph class. This leads to two fundamental questions, which lie at the heart of our Dagstuhl Seminar: for which graph classes can an NP-hard vertex partitioning problem be solved in polynomial time, and for which graph classes does the problem remain NP-hard?

In our seminar, we aim to discover, in a systematic way, general properties of graph classes from which we can determine the tractability or hardness of vertex partitioning problems. For this purpose, we bring together researchers from Discrete Mathematics and Theoretical Computer Science. Topics of the seminar will include:

• Vertex Partitioning Problems
• Hereditary Graph Classes
• Width Parameters
• Graph Decompositions
• Minimal Separators
• Parameterized Complexity

We plan an appropriate number of survey talks, presentations of recent results, open problem sessions, and ample time for discussions and problem solving. As concrete outcomes we expect to develop new, general methodology for solving vertex partitioning problems. This will also increase our understanding of how the complexities of these problems are related to each other when the input is restricted to some special graph class.

Maria Chudnovsky, Neeldhara Misra, Daniel Paulusma, and Oliver Schaudt

##### Participants
• (Princeton University, US) [dblp]
• (Indian Institute of Techology Madras, IN) [dblp]
• Bogdan Alecu (University of Leeds, GB)
• (TU Bergakademie Freiberg, DE) [dblp]
• (Victoria University - Wellington, NZ) [dblp]
• (Universität Ulm, DE) [dblp]
• (Princeton University, US) [dblp]
• (Newcastle University, GB) [dblp]
• (University of California - Santa Barbara, US) [dblp]
• (KU Leuven, BE) [dblp]
• (University of Bergen, NO) [dblp]
• (TU Eindhoven, NL) [dblp]
• (University of Bergen, NO)
• (Masaryk University - Brno, CZ) [dblp]
• (University of Bergen, NO)
• (IT University of Copenhagen, DK) [dblp]
• (University of California - Santa Barbara, US) [dblp]
• (Durham University, GB) [dblp]
• (University of Warsaw, PL) [dblp]
• (University of Warsaw, PL & Charles University - Praha, CZ)
• (Queen's University of Belfast, GB) [dblp]
• (Utrecht University, NL)
• Sukanya Pandey (Utrecht University, NL)
• (Durham University, GB) [dblp]
• (University of Warsaw, PL) [dblp]
• (University of Warsaw, PL) [dblp]
• (Warsaw University of Technology, PL) [dblp]
• (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
• Oliver Schaudt (Bayer AG - Leverkusen, DE) [dblp]
• (Princeton University, US) [dblp]
• (MPI für Informatik - Saarbrücken, DE) [dblp]
• Siani Smith (University of Bristol, GB)
• (University of Bergen, NO) [dblp]
• (ENS - Lyon, FR) [dblp]
• (Utrecht University, NL) [dblp]
• (University of Leeds, GB) [dblp]

##### Related Seminars
• Dagstuhl Seminar 19271: Graph Colouring: from Structure to Algorithms (2019-06-30 - 2019-07-05) (Details)

##### Classification
• Computational Complexity
• Data Structures and Algorithms
• Discrete Mathematics

##### Keywords
• computational complexity
• hereditary graph classes
• parameterized algorithms
• polynomial-time algorithms
• vertex partitioning