Document

**Published in:** Dagstuhl Reports, Volume 12, Issue 11 (2023)

This report documents the program and the outcomes of Dagstuhl Seminar 22481 "Vertex Partitioning in Graphs: From Structure to Algorithms", which was held from 27 November to 2 December 2023. The report contains abstracts for presentations about recent structural and algorithmic developments for a variety of vertex partitioning problems. It also contains a collection of open problems which were posed during the seminar.

Maria Chudnovsky, Neeldhara Misra, Daniel Paulusma, Oliver Schaudt, and Akanksha Agrawal. Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481). In Dagstuhl Reports, Volume 12, Issue 11, pp. 109-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{chudnovsky_et_al:DagRep.12.11.109, author = {Chudnovsky, Maria and Misra, Neeldhara and Paulusma, Daniel and Schaudt, Oliver and Agrawal, Akanksha}, title = {{Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481)}}, pages = {109--123}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {11}, editor = {Chudnovsky, Maria and Misra, Neeldhara and Paulusma, Daniel and Schaudt, Oliver and Agrawal, Akanksha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.109}, URN = {urn:nbn:de:0030-drops-178384}, doi = {10.4230/DagRep.12.11.109}, annote = {Keywords: computational complexity, hereditary graph classes, parameterized algorithms, polynomial-time algorithms, vertex partitioning} }

Document

**Published in:** LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k-1 edges of the graph may fail. We extend the simple uniform failure model of the s-t EDP as follows: the edge set of the graph is partitioned into vulnerable, and safe edges, and a set of at most k vulnerable edges may fail, while safe edges do not fail. In particular we study the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest s-t Path problem in this non-uniform failure model as well as the Fault-Tolerant Flow (FTF) problem, the counterpart of s-t EDP. We present complexity results alongside exact and approximation algorithms for both problems. We emphasize the vast increase in complexity of the problems compared to s-t EDP.

David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{adjiashvili_et_al:LIPIcs.SWAT.2022.5, author = {Adjiashvili, David and Hommelsheim, Felix and M\"{u}hlenthaler, Moritz and Schaudt, Oliver}, title = {{Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {5:1--5:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.5}, URN = {urn:nbn:de:0030-drops-161659}, doi = {10.4230/LIPIcs.SWAT.2022.5}, annote = {Keywords: graph algorithms, network design, fault tolerance, approximation algorithms} }

Document

**Published in:** Dagstuhl Reports, Volume 9, Issue 6 (2020)

This report documents the program and the outcomes of Dagstuhl Seminar 19271 "Graph Colouring: from Structure to Algorithm", which was held from 30 June to 5 July 2019. The report contains abstracts for presentations about recent structural and algorithmic developments for the Graph Colouring problem and variants of it. It also contains a collection of open problems on graph colouring which were posed during the seminar.

Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt. Graph Colouring: from Structure to Algorithms (Dagstuhl Seminar 19271). In Dagstuhl Reports, Volume 9, Issue 6, pp. 125-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{chudnovsky_et_al:DagRep.9.6.125, author = {Chudnovsky, Maria and Paulusma, Daniel and Schaudt, Oliver}, title = {{Graph Colouring: from Structure to Algorithms (Dagstuhl Seminar 19271)}}, pages = {125--142}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {6}, editor = {Chudnovsky, Maria and Paulusma, Daniel and Schaudt, Oliver}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.6.125}, URN = {urn:nbn:de:0030-drops-114905}, doi = {10.4230/DagRep.9.6.125}, annote = {Keywords: (certifying / parameterized / polynomial-time) algorithms, computational complexity, graph colouring, hereditary graph classes} }

Document

**Published in:** LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We consider the task of adding a minimum cost edge-set to the graph, such that the adversary never wins. We show that this problem is equivalent to covering a digraph with non-trivial strongly connected components at minimal cost. We provide efficient exact and approximation algorithms for this task. In particular, for the unit-cost problem, we give a log_2 n-factor approximation algorithm and a polynomial-time algorithm for chordal-bipartite graphs. Furthermore, we give a fixed parameter algorithm for the problem parameterized by the treewidth of the input graph. For general non-negative weights we give tight upper and lower approximation bounds relative to the Directed Steiner Forest problem. Additionally we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm. To obtain our results, we exploit a close relation to the classical Strong Connectivity Augmentation problem as well as directed Steiner problems.

Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. How to Secure Matchings Against Edge Failures. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hommelsheim_et_al:LIPIcs.STACS.2019.38, author = {Hommelsheim, Felix and M\"{u}hlenthaler, Moritz and Schaudt, Oliver}, title = {{How to Secure Matchings Against Edge Failures}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {38:1--38:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.38}, URN = {urn:nbn:de:0030-drops-102772}, doi = {10.4230/LIPIcs.STACS.2019.38}, annote = {Keywords: Matchings, Robustness, Connectivity Augmentation, Graph Algorithms, Treewidth} }

Document

**Published in:** LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

In a Stackelberg Pricing Game a distinguished player, the leader, chooses prices for a set of items, and the other players, the followers, each seeks to buy a minimum cost feasible subset of the items. The goal of the leader is to maximize her revenue, which is determined by the sold items and their prices. Most previously studied cases of such games can be captured by a combinatorial model where we have a base set of items, some with fixed prices, some priceable, and constraints on the subsets that are feasible for each follower. In this combinatorial setting, Briest et al. and Balcan et al. independently showed that the maximum revenue can be approximated to a factor of H_k ~ log(k), where k is the number of priceable items.
Our results are twofold. First, we strongly generalize the model by letting the follower minimize any continuous function plus a linear term over any compact subset of R_(n>=0); the coefficients (or prices) in the linear term are chosen by the leader and determine her revenue. In particular, this includes the fundamental case of linear programs. We give a tight lower bound on the revenue of the leader, generalizing the results of Briest et al. and Balcan et al. Besides, we prove that it is strongly NP-hard to decide whether the optimum revenue exceeds the lower bound by an arbitrarily small factor. Second, we study the parameterized complexity of computing the optimal revenue with respect to the number k of priceable items. In the combinatorial setting, given an efficient algorithm for optimal follower solutions, the maximum revenue can be found by enumerating the 2^k subsets of priceable items and computing optimal prices via a result of Briest et al., giving time O(2^k|I|^c ) where |I| is the input size. Our main result here is a W[1]-hardness proof for the case where the followers minimize a linear program, ruling out running time f(k)|I|^c unless FPT = W[1] and ruling out time |I|^o(k) under the Exponential-Time Hypothesis.

Toni Böhnlein, Stefan Kratsch, and Oliver Schaudt. Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bohnlein_et_al:LIPIcs.ICALP.2017.46, author = {B\"{o}hnlein, Toni and Kratsch, Stefan and Schaudt, Oliver}, title = {{Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {46:1--46:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.46}, URN = {urn:nbn:de:0030-drops-73771}, doi = {10.4230/LIPIcs.ICALP.2017.46}, annote = {Keywords: Algorithmic pricing, Stackelberg games, Approximation algorithms, Rev- enue maximization, Parameterized complexity} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail