15 Search Results for "Schaudt, Oliver"

Document
DOI: 10.4230/LIPIcs.STACS.2026.73
Colouring Probe H-Free Graphs

Authors: Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
The NP-complete problems Colouring and k-Colouring (k ≥ 3) are well studied on H-free graphs, i.e., graphs that do not contain some fixed graph H as an induced subgraph. We research to what extent the known polynomial-time algorithms for H-free graphs can be generalized if we only know some of the edges of the input graph. We do this by considering the classical probe graph model introduced in the early nineties. For a graph H, a partitioned probe H-free graph (G,P,N) consists of a graph G = (V,E), together with a set P ⊆ V of probes and an independent set N = V ⧵ P of non-probes, such that G+F is H-free for some edge set F ⊆ binom(N,2). We show the following: - We fully classify Colouring on partitioned probe H-free graphs and show that the obtained complexity dichotomy differs from the known dichotomy of Colouring for H-free graphs. - We fully classify 3-Colouring on partitioned probe P_t-free graphs: we prove polynomial-time solvability for t ≤ 5 and NP-completeness for t ≥ 6. In contrast, 3-Colouring on P_t-free graphs is known to be polynomial-time solvable for t ≤ 7 and quasi-polynomial-time solvable for t ≥ 8. Our main result is our polynomial-time algorithm for 3-Colouring on partitioned P₅-free graphs. For this result, and also for all our other polynomial-time results, we do not need to know the edge set F; we only need to know its existence. Moreover, the class of probe P₅-free graphs includes not only paths of arbitrary length but even all bipartite graphs and is much richer than the class of P₅-free graphs. The latter is also evidenced by the fact that there exist graph problems, such as Matching Cut, that are known to be polynomial-time solvable for P₅-free graphs but NP-complete for partitioned probe P₅-free graphs. In particular, unlike the class of 3-colourable P₅-free graphs, the class of 3-colourable probe P₅-free graphs has unbounded mim-width. Hence, our polynomial-time result for 3-Colouring for probe P₅-free graphs suggests that there may be another, deeper overarching reason why 3-Colouring is polynomial-time solvable for P₅-free graphs.
Cite as

Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen. Colouring Probe H-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{paulusma_et_al:LIPIcs.STACS.2026.73,
  author =	{Paulusma, Dani\"{e}l and Rauch, Johannes and van Leeuwen, Erik Jan},
  title =	{{Colouring Probe H-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{73:1--73:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.73},
  URN =		{urn:nbn:de:0030-drops-255621},
  doi =		{10.4230/LIPIcs.STACS.2026.73},
  annote =	{Keywords: colouring, probe graph, forbidden induced subgraph, complexity dichotomy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.74
List Coloring Ordered Graphs with Forbidden Induced Subgraphs

Authors: Marta Piecyk and Paweł Rzążewski

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In the List k-Coloring problem we are given a graph whose every vertex is equipped with a list, which is a subset of {1,…,k}. We need to decide if G admits a proper coloring, where every vertex receives a color from its list. The complexity of the problem in classes defined by forbidding induced subgraphs is a widely studied topic in algorithmic graph theory. Recently, Hajebi, Li, and Spirkl [SIAM J. Discr. Math. 38 (2024)] initiated the study of List 3-Coloring in ordered graphs, i.e., graphs with fixed linear ordering of vertices. Forbidding ordered induced subgraphs allows us to investigate the boundary of tractability more closely. We continue this direction of research, focusing mostly on the case of List 4-Coloring. We present several algorithmic and hardness results, which altogether provide an almost complete dichotomy for classes defined by forbidding one fixed ordered graph: our investigations leave one minimal open case.
Cite as

Marta Piecyk and Paweł Rzążewski. List Coloring Ordered Graphs with Forbidden Induced Subgraphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 74:1-74:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{piecyk_et_al:LIPIcs.STACS.2026.74,
  author =	{Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{List Coloring Ordered Graphs with Forbidden Induced Subgraphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{74:1--74:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.74},
  URN =		{urn:nbn:de:0030-drops-255634},
  doi =		{10.4230/LIPIcs.STACS.2026.74},
  annote =	{Keywords: coloring, ordered graphs, forbidden induced subgraphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.1
Triangle Detection in H-Free Graphs

Authors: Amir Abboud, Ron Safier, and Nathan Wallheimer

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We initiate the study of combinatorial algorithms for Triangle Detection in H-free graphs. The goal is to decide if a graph that forbids a fixed pattern H as a subgraph contains a triangle, using only "combinatorial" methods that notably exclude fast matrix multiplication. Our work aims to classify which patterns admit a subcubic speedup, working towards a dichotomy theorem. On the lower bound side, we show that if H is not 3-colorable or contains more than one triangle, the complexity of the problem remains unchanged, and no combinatorial speedup is likely possible. On the upper bound side, we develop an embedding approach that results in a strongly subcubic, combinatorial algorithm for a rich class of "embeddable" patterns. Specifically, for an embeddable pattern of size k, our algorithm runs in Õ(n^{3-1/(2^{k-3)}}) time, where Õ(⋅) hides poly-logarithmic factors. This algorithm also extends to listing all the triangles within the same time bound. We supplement this main result with two generalizations: - A generalization to patterns that are embeddable up to a single obstacle that arises from a triangle in the pattern. This completes our classification for small patterns, yielding a dichotomy theorem for all patterns of size up to eight. - An H-sensitive algorithm for embeddable patterns, which runs faster when the number of copies of H is significantly smaller than the maximum possible Ω(n^{k}). Finally, we focus on the special case of odd cycles. We present specialized Triangle Detection algorithms that are very efficient: - A combinatorial algorithm for C_{2k+1}-free graphs that runs in Õ(m+n^{1+2/k}) time for every k ≥ 2, where m is the number of edges in the graph. - A combinatorial C₅-sensitive algorithm that runs in Õ(n² + n^{4/3} t^{1/3}) time, where t is the number of 5-cycles in the graph.
Cite as

Amir Abboud, Ron Safier, and Nathan Wallheimer. Triangle Detection in H-Free Graphs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.ITCS.2026.1,
  author =	{Abboud, Amir and Safier, Ron and Wallheimer, Nathan},
  title =	{{Triangle Detection in H-Free Graphs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.1},
  URN =		{urn:nbn:de:0030-drops-252885},
  doi =		{10.4230/LIPIcs.ITCS.2026.1},
  annote =	{Keywords: fine-grained complexity, triangle detection, H-free graphs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.20
Sparse Induced Subgraphs in P₇-Free Graphs of Bounded Clique Number

Authors: Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, and Paweł Rzążewski

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph that satisfies some property definable in CMSO₂ logic. It is believed that each problem expressible with this formalism can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph. This belief is supported by the existence of a quasipolynomial-time algorithm by Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rzążewski [STOC 2021], and a recent polynomial-time algorithm for P₆-free graphs by Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rzążewski [SODA 2024]. In this work we extend polynomial-time tractability of all such problems to P₇-free graphs of bounded clique number.
Cite as

Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk, Marcin Pilipczuk, and Paweł Rzążewski. Sparse Induced Subgraphs in P₇-Free Graphs of Bounded Clique Number. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chudnovsky_et_al:LIPIcs.ISAAC.2025.20,
  author =	{Chudnovsky, Maria and Czy\.{z}ewska, Jadwiga and Kluk, Kacper and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Sparse Induced Subgraphs in P₇-Free Graphs of Bounded Clique Number}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.20},
  URN =		{urn:nbn:de:0030-drops-249282},
  doi =		{10.4230/LIPIcs.ISAAC.2025.20},
  annote =	{Keywords: P\underlinet-free graphs, maximum weight induced subgraph, maximum weight independent set}
}
Document
DOI: 10.4230/DagRep.15.1.105
Solving Problems on Graphs: From Structure to Algorithms (Dagstuhl Seminar 25041)

Authors: Akanksha Agrawal, Maria Chudnovsky, Daniël Paulusma, Oliver Schaudt, and Julien Codsi

Published in: Dagstuhl Reports, Volume 15, Issue 1 (2025)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 25041 "Solving Problems on Graphs: From Structure to Algorithms", which was held from 19 January to 24 January 2025. The report contains abstracts for presentations about recent structural and algorithmic developments for a variety of graph problems. It also contains a collection of open problems which were posed during the seminar.
Cite as

Akanksha Agrawal, Maria Chudnovsky, Daniël Paulusma, Oliver Schaudt, and Julien Codsi. Solving Problems on Graphs: From Structure to Algorithms (Dagstuhl Seminar 25041). In Dagstuhl Reports, Volume 15, Issue 1, pp. 105-121, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{agrawal_et_al:DagRep.15.1.105,
  author =	{Agrawal, Akanksha and Chudnovsky, Maria and Paulusma, Dani\"{e}l and Schaudt, Oliver and Codsi, Julien},
  title =	{{Solving Problems on Graphs: From Structure to Algorithms (Dagstuhl Seminar 25041)}},
  pages =	{105--121},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{1},
  editor =	{Agrawal, Akanksha and Chudnovsky, Maria and Paulusma, Dani\"{e}l and Schaudt, Oliver and Codsi, Julien},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.1.105},
  URN =		{urn:nbn:de:0030-drops-236749},
  doi =		{10.4230/DagRep.15.1.105},
  annote =	{Keywords: computational complexity, graph algorithms, graph classes, graph containment relations, graph width parameters}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.83
Fault-Tolerant Matroid Bases

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, and Laure Morelle

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We investigate the problem of constructing fault-tolerant bases in matroids. Given a matroid ℳ and a redundancy parameter k, a k-fault-tolerant basis is a minimum-size set of elements such that, even after the removal of any k elements, the remaining subset still spans the entire ground set. Since matroids generalize linear independence across structures such as vector spaces, graphs, and set systems, this problem unifies and extends several fault-tolerant concepts appearing in prior research. Our main contribution is a fixed-parameter tractable (FPT) algorithm for the k-fault-tolerant basis problem, parameterized by both k and the rank r of the matroid. This two-variable parameterization by k + r is shown to be tight in the following sense. On the one hand, the problem is already NP-hard for k = 1. On the other hand, it is Para-NP-hard for r ≥ 3 and polynomial-time solvable for r ≤ 2.
Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, and Laure Morelle. Fault-Tolerant Matroid Bases. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ESA.2025.83,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Morelle, Laure},
  title =	{{Fault-Tolerant Matroid Bases}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{83:1--83:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.83},
  URN =		{urn:nbn:de:0030-drops-245511},
  doi =		{10.4230/LIPIcs.ESA.2025.83},
  annote =	{Keywords: Parameterized Complexity, matroids, robust bases}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.158
Restricted CSPs and F-Free Digraph Algorithmics

Authors: Santiago Guzmán-Pro and Barnaby Martin

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to ℙ_k-free and ℙ_k-subgraph-free graphs. We consider the directed version of this research line, by addressing the question is it true that digraph homomorphism problems CSP(H) have a P versus NP-complete dichotomy when the input is restricted to ℙ→_k-free (resp. ℙ→_k-subgraph-free) digraphs? Our main contribution in this direction shows that if CSP(H) is NP-complete, then there is a positive integer N such that CSP(H) remains NP-hard even for ℙ→_N-subgraph-free digraphs. Moreover, CSP(H) becomes polynomial-time solvable for ℙ→_{N-1}-subgraph-free acyclic digraphs. We then verify the questions above for digraphs on three vertices and a family of smooth tournaments. We prove these results by establishing a connection between F-(subgraph)-free algorithmics and constraint satisfaction theory. On the way, we introduce restricted CSPs, i.e., problems of the form CSP(H) restricted to yes-instances of CSP(H') - these were called restricted homomorphism problems by Hell and Nešetřil. Another main result of this paper presents a P versus NP-complete dichotomy for these problems. Moreover, this complexity dichotomy is accompanied by an algebraic dichotomy in the spirit of the finite domain CSP dichotomy.
Cite as

Santiago Guzmán-Pro and Barnaby Martin. Restricted CSPs and F-Free Digraph Algorithmics. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 158:1-158:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guzmanpro_et_al:LIPIcs.ICALP.2025.158,
  author =	{Guzm\'{a}n-Pro, Santiago and Martin, Barnaby},
  title =	{{Restricted CSPs and F-Free Digraph Algorithmics}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{158:1--158:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.158},
  URN =		{urn:nbn:de:0030-drops-235352},
  doi =		{10.4230/LIPIcs.ICALP.2025.158},
  annote =	{Keywords: Digraph homomorphisms, constraint satisfaction problems, subgraph-free algorithmics}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.51
Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures

Authors: Felix Hommelsheim, Zhenwei Liu, Nicole Megow, and Guochuan Zhang

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a non-uniform failure model. We introduce the (p,q)-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains p-edge-connectivity between given terminal pairs against edge failures, assuming at most q unprotected edges can fail. We design polynomial-time exact algorithms for the cases where p and q are small and approximation algorithms for general values of p and q. Additionally, we show that when both p and q are part of the input, even deciding whether a given solution is feasible is NP-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either p or q is constant, for which our new hardness result now provides justification.
Cite as

Felix Hommelsheim, Zhenwei Liu, Nicole Megow, and Guochuan Zhang. Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hommelsheim_et_al:LIPIcs.STACS.2025.51,
  author =	{Hommelsheim, Felix and Liu, Zhenwei and Megow, Nicole and Zhang, Guochuan},
  title =	{{Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{51:1--51:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.51},
  URN =		{urn:nbn:de:0030-drops-228761},
  doi =		{10.4230/LIPIcs.STACS.2025.51},
  annote =	{Keywords: Network Design, Edge Failures, Graph Connectivity, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.55
Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes

Authors: Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski, and Oliver Schaudt

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). Note that if H is the triangle, then H-colorings are equivalent to 3-colorings. In this paper we are interested in the case that H is the five-vertex cycle C₅. A minimal obstruction to C₅-coloring is a graph that does not have a C₅-coloring, but every proper induced subgraph thereof has a C₅-coloring. In this paper we are interested in minimal obstructions to C₅-coloring in F-free graphs, i.e., graphs that exclude some fixed graph F as an induced subgraph. Let P_t denote the path on t vertices, and let S_{a,b,c} denote the graph obtained from paths P_{a+1},P_{b+1},P_{c+1} by identifying one of their endvertices. We show that there is only a finite number of minimal obstructions to C₅-coloring among F-free graphs, where F ∈ {P₈, S_{2,2,1}, S_{3,1,1}} and explicitly determine all such obstructions. This extends the results of Kamiński and Pstrucha [Discr. Appl. Math. 261, 2019] who proved that there is only a finite number of P₇-free minimal obstructions to C₅-coloring, and of Dębski et al. [ISAAC 2022 Proc.] who showed that the triangle is the unique S_{2,1,1}-free minimal obstruction to C₅-coloring. We complement our results with a construction of an infinite family of minimal obstructions to C₅-coloring, which are simultaneously P_{13}-free and S_{2,2,2}-free. We also discuss infinite families of F-free minimal obstructions to H-coloring for other graphs H.
Cite as

Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzążewski, and Oliver Schaudt. Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goedgebeur_et_al:LIPIcs.MFCS.2024.55,
  author =	{Goedgebeur, Jan and Jooken, Jorik and Okrasa, Karolina and Rz\k{a}\.{z}ewski, Pawe{\l} and Schaudt, Oliver},
  title =	{{Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.55},
  URN =		{urn:nbn:de:0030-drops-206110},
  doi =		{10.4230/LIPIcs.MFCS.2024.55},
  annote =	{Keywords: graph homomorphism, critical graphs, hereditary graph classes}
}
Document
DOI: 10.4230/DagRep.12.11.109
Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481)

Authors: Maria Chudnovsky, Neeldhara Misra, Daniel Paulusma, Oliver Schaudt, and Akanksha Agrawal

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.SWAT.2022.5
Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults

Authors: David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt

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

Abstract
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.
Cite as

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
DOI: 10.4230/DagRep.9.6.125
Graph Colouring: from Structure to Algorithms (Dagstuhl Seminar 19271)

Authors: Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.STACS.2019.38
How to Secure Matchings Against Edge Failures

Authors: Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.ISAAC.2018.5
Colouring (P_r+P_s)-Free Graphs

Authors: Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, and Veronika Slívová

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list L(u) subseteq {1,...,k}, then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. We prove that List 3-Colouring is polynomial-time solvable for (P_2+P_5)-free graphs and for (P_3+P_4)-free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices. We also prove that 5-Colouring is NP-complete for (P_3+P_5)-free graphs.
Cite as

Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, and Veronika Slívová. Colouring (P_r+P_s)-Free Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{klimosova_et_al:LIPIcs.ISAAC.2018.5,
  author =	{Klimo\v{s}ov\'{a}, Tereza and Mal{\'\i}k, Josef and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana and Paulusma, Dani\"{e}l and Sl{\'\i}vov\'{a}, Veronika},
  title =	{{Colouring (P\underliner+P\underlines)-Free Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.5},
  URN =		{urn:nbn:de:0030-drops-99533},
  doi =		{10.4230/LIPIcs.ISAAC.2018.5},
  annote =	{Keywords: vertex colouring, H-free graph, linear forest}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.46
Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting

Authors: Toni Böhnlein, Stefan Kratsch, and Oliver Schaudt

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

Abstract
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.
Cite as

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}
}
  • Refine by Type
  • 15 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 5 2025
  • 1 2024
  • 1 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 7 Schaudt, Oliver
  • 4 Chudnovsky, Maria
  • 3 Hommelsheim, Felix
  • 3 Paulusma, Daniël
  • 3 Rzążewski, Paweł
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs
  • 3 DagRep

  • Refine by Classification
  • 6 Mathematics of computing → Graph algorithms
  • 3 Mathematics of computing → Graph theory
  • 3 Theory of computation → Fixed parameter tractability
  • 3 Theory of computation → Graph algorithms analysis
  • 3 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 3 computational complexity
  • 3 hereditary graph classes
  • 2 graph algorithms
  • 1 (certifying / parameterized / polynomial-time) algorithms
  • 1 Algorithmic pricing
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact