Dagstuhl Seminar 22481
Vertex Partitioning in Graphs: From Structure to Algorithms
( Nov 27 – Dec 02, 2022 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/22481
Organizers
- Maria Chudnovsky (Princeton University, US)
- Neeldhara Misra (Indian Institute of Techology - Madras, IN)
- Daniel Paulusma (Durham University, GB)
- Oliver Schaudt (Bayer AG - Leverkusen, DE)
Contact
- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Impacts
- Max Weight Independent Set in sparse graphs with no long claws : article - Abrishami, Tara; Chudnovsky, Maria; Pilipczuk, Marcin; Rzazewski, Pawel - Cornell University : arXiv.org, 2023. - 13 pp..
- Minimal obstructions to C5-coloring in hereditary graph classes - Goedgebeur, Jan; Kooken, Jorik; Okrasa, Karolina; Rzążewski, Paweł; Schaudt, Oliver - Cornell University : arXiv.org, 2024. - 27 pp..
Schedule
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.
Most vertex partitioning problems are computationally hard. The central research aim of our seminar was to increase our understanding of the computational complexity of these problems. The main approach followed at the seminar for achieving this was to restrict the input of some problem to some special graph class. The fundamental question then becomes whether such a restriction makes the problem tractable or whether the problem remains hard. In order to approach this question, we followed a systematic way by considering graph classes characterized by some finite family H of obstructions (as induced subgraph, subgraph, minor etc.).
In line with the seminar's research aim, the seminar brought together researchers from Discrete Mathematics, working in structural graph theory, and researchers from Theoretical Computer Science, working in algorithmic graph theory. In total, 36 participants from 12 different countries attended the seminar.
The scientific program of the seminar consisted of 23 sessions: 5 survey talks of fifty minutes, 13 contributed talks of at most thirty minutes and 5 open problem sessions. This left ample time for discussions and problem solving. Participants presented the progress that made during the workshop during several "progress report" sessions. One the the questions discussed at the workshop was a long-time open problem concerning the complexity of detecting whether a graph contains two long induced cycles with no edges between them. In the course of the workshop Khang Le informed us that he found a polynomial-time algorithm to solve this problem; Le's proof was presented by Paul Seymour.
Each of the five survey talks covered a particular structural or algorithmic key aspect of the seminar in order to enable collaborations of researchers with different backgrounds. On Monday, Paul Seymour presented a number of recent developments on the Erdös-Hajnal conjecture including several open problems. On the same day, Tara Abrishami described a variety of techniques for proving the boundedness or unboundedness of treewidth of hereditary graph classes. On Tuesday, Daniel Lokshtanov explained how algorithms for the Independent Set problem on Pk-free graphs developed over time, and also gave extensions of these results to other graph classes. On the same day, Daniel Král' surveyed basic results and open problems for two classical graph colouring parameters, the fractional and circular chromatic number of a graph, and one recent graph colouring parameter, the gyrochromatic number. On Wednesday, Henning Bruhn-Fujimoto gave a survey talk on Erdös-Posa type questions, which relate to graph packing and graph covering dualities. In this talk, many open problems were given as well.
The five general open problem sessions took place on Monday, Tuesday and Wednesday. Details of the presented problems can be found in the report, together with abstracts of all the talks.
We are grateful to Gerhard Woeginger for all his help with our seminar when it was originally planned to take place from 31 January to 5 February 2021. Our seminar was postponed to November 2022 due to the pandemic, and sadly, Gerhard passed away on 1 April 2022.
We also thank Akanksha Agrawal for her help with the Dagstuhl report of our seminar.
Creative Commons BY 4.0
Maria Chudnovsky, Neeldhara Misra, Daniel Paulusma, and Oliver Schaudt
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
- Tara Abrishami (Princeton University, US) [dblp]
- Akanksha Agrawal (Indian Institute of Techology Madras, IN) [dblp]
- Bogdan Alecu (University of Leeds, GB)
- Christoph Brause (TU Bergakademie Freiberg, DE) [dblp]
- Nick Brettell (Victoria University - Wellington, NZ) [dblp]
- Henning Bruhn-Fujimoto (Universität Ulm, DE) [dblp]
- Maria Chudnovsky (Princeton University, US) [dblp]
- Konrad Dabrowski (Newcastle University, GB) [dblp]
- Peter Gartland (University of California - Santa Barbara, US) [dblp]
- Jan Goedgebeur (KU Leuven, BE) [dblp]
- Petr A. Golovach (University of Bergen, NO) [dblp]
- Bart Jansen (TU Eindhoven, NL) [dblp]
- Tuukka Korhonen (University of Bergen, NO) [dblp]
- Daniel Král' (Masaryk University - Brno, CZ) [dblp]
- Madhumita Kundu (University of Bergen, NO) [dblp]
- Paloma Lima (IT University of Copenhagen, DK) [dblp]
- Daniel Lokshtanov (University of California - Santa Barbara, US) [dblp]
- Barnaby Martin (Durham University, GB) [dblp]
- Tomas Masarik (University of Warsaw, PL) [dblp]
- Jana Masarikova (University of Warsaw, PL & Charles University - Praha, CZ)
- Andrea Munaro (Queen's University of Belfast, GB) [dblp]
- Jelle Oostveen (Utrecht University, NL)
- Sukanya Pandey (Utrecht University, NL)
- Daniel Paulusma (Durham University, GB) [dblp]
- Marcin Pilipczuk (University of Warsaw, PL) [dblp]
- Michal Pilipczuk (University of Warsaw, PL) [dblp]
- Pawel Rzazewski (Warsaw University of Technology, PL) [dblp]
- Saket Saurabh (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Oliver Schaudt (Bayer AG - Leverkusen, DE) [dblp]
- Paul Seymour (Princeton University, US) [dblp]
- Roohani Sharma (MPI für Informatik - Saarbrücken, DE) [dblp]
- Siani Smith (University of Bristol, GB)
- Jan Arne Telle (University of Bergen, NO) [dblp]
- Nicolas Trotignon (ENS - Lyon, FR) [dblp]
- Erik Jan van Leeuwen (Utrecht University, NL) [dblp]
- Kristina Vuskovic (University of Leeds, GB) [dblp]
Related Seminars
Classification
- Computational Complexity
- Data Structures and Algorithms
- Discrete Mathematics
Keywords
- computational complexity
- hereditary graph classes
- parameterized algorithms
- polynomial-time algorithms
- vertex partitioning
