21 Search Results for "Rzazewski, Pawel"


Document
Max Weight Independent Set in Sparse Graphs with No Long Claws

Authors: Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)


Abstract
We revisit the recent polynomial-time algorithm for the Max Weight Independent Set (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component is a subdivided claw as an induced subgraph [Abrishami, Chudnovsky, Dibek, Rzążewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time n^{𝒪(Δ²)}, where n is the number of vertices of the instance and Δ is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph.

Cite as

Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski. Max Weight Independent Set in Sparse Graphs with No Long Claws. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{abrishami_et_al:LIPIcs.STACS.2024.4,
  author =	{Abrishami, Tara and Chudnovsky, Maria and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Max Weight Independent Set in Sparse Graphs with No Long Claws}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.4},
  URN =		{urn:nbn:de:0030-drops-197148},
  doi =		{10.4230/LIPIcs.STACS.2024.4},
  annote =	{Keywords: Max Weight Independent Set, subdivided claw, hereditary classes}
}
Document
Coloring and Recognizing Mixed Interval Graphs

Authors: Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)


Abstract
A mixed interval graph is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particularly interested in scenarios where edges and arcs are defined by the geometry of intervals. In a proper coloring of a mixed interval graph G, an interval u receives a lower (different) color than an interval v if G contains arc (u,v) (edge {u,v}). Coloring of mixed graphs has applications, for example, in scheduling with precedence constraints; see a survey by Sotskov [Mathematics, 2020]. For coloring general mixed interval graphs, we present a min {ω(G), λ(G)+1}-approximation algorithm, where ω(G) is the size of a largest clique and λ(G) is the length of a longest directed path in G. For the subclass of bidirectional interval graphs (introduced recently for an application in graph drawing), we show that optimal coloring is NP-hard. This was known for general mixed interval graphs. We introduce a new natural class of mixed interval graphs, which we call containment interval graphs. In such a graph, there is an arc (u,v) if interval u contains interval v, and there is an edge {u,v} if u and v overlap. We show that these graphs can be recognized in polynomial time, that coloring them with the minimum number of colors is NP-hard, and that there is a 2-approximation algorithm for coloring.

Cite as

Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen, Paweł Rzążewski, Alexander Wolff, and Johannes Zink. Coloring and Recognizing Mixed Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{gutowski_et_al:LIPIcs.ISAAC.2023.36,
  author =	{Gutowski, Grzegorz and Junosza-Szaniawski, Konstanty and Klesen, Felix and Rz\k{a}\.{z}ewski, Pawe{\l} and Wolff, Alexander and Zink, Johannes},
  title =	{{Coloring and Recognizing Mixed Interval Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.36},
  URN =		{urn:nbn:de:0030-drops-193388},
  doi =		{10.4230/LIPIcs.ISAAC.2023.36},
  annote =	{Keywords: Interval Graphs, Mixed Graphs, Graph Coloring}
}
Document
Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws

Authors: Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). In the H-Coloring problem the graph H is fixed and we ask whether an instance graph G admits an H-coloring. A generalization of this problem is H-ColoringExt, where some vertices of G are already mapped to vertices of H and we ask if this partial mapping can be extended to an H-coloring. We study the complexity of variants of H-Coloring in F-free graphs, i.e., graphs excluding a fixed graph F as an induced subgraph. For integers a,b,c ⩾ 1, by S_{a,b,c} we denote the graph obtained by identifying one endvertex of three paths on a+1, b+1, and c+1 vertices, respectively. For odd k ⩾ 5, by W_k we denote the graph obtained from the k-cycle by adding a universal vertex. As our main algorithmic result we show that W_5-ColoringExt is polynomial-time solvable in S_{2,1,1}-free graphs. This result exhibits an interesting non-monotonicity of H-ColoringExt with respect to taking induced subgraphs of H. Indeed, W_5 contains a triangle, and K_3-Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., S_{1,1,1}-free) graphs. Our algorithm is based on two main observations: 1) W_5-ColoringExt in S_{2,1,1}-free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and 2) the latter problem can be solved in polynomial time in S_{2,1,1}-free graphs. We complement this algorithmic result with several negative ones. In particular, we show that W_5-Coloring is NP-hard in P_t-free graphs for some constant t and W_5-ColoringExt is NP-hard in S_{3,3,3}-free graphs of bounded degree. This is again uncommon, as usually problems that are NP-hard in S_{a,b,c}-free graphs for some constant a,b,c are already hard in claw-free graphs

Cite as

Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{debski_et_al:LIPIcs.ISAAC.2022.14,
  author =	{D\k{e}bski, Micha{\l} and Lonc, Zbigniew and Okrasa, Karolina and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.14},
  URN =		{urn:nbn:de:0030-drops-172996},
  doi =		{10.4230/LIPIcs.ISAAC.2022.14},
  annote =	{Keywords: graph homomorphism, forbidden induced subgraphs, precoloring extension}
}
Document
List Locally Surjective Homomorphisms in Hereditary Graph Classes

Authors: Pavel Dvořák, Tomáš Masařík, Jana Novotná, Monika Krawczyk, Paweł Rzążewski, and Aneta Żuk

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
A locally surjective homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H) that is surjective in the neighborhood of each vertex in G. In the list locally surjective homomorphism problem, denoted by LLSHom(H), the graph H is fixed and the instance consists of a graph G whose every vertex is equipped with a subset of V(H), called list. We ask for the existence of a locally surjective homomorphism from G to H, where every vertex of G is mapped to a vertex from its list. In this paper, we study the complexity of the LLSHom(H) problem in F-free graphs, i.e., graphs that exclude a fixed graph F as an induced subgraph. We aim to understand for which pairs (H,F) the problem can be solved in subexponential time. We show that for all graphs H, for which the problem is NP-hard in general graphs, it cannot be solved in subexponential time in F-free graphs for F being a bounded-degree forest, unless the ETH fails. The initial study reveals that a natural subfamily of bounded-degree forests F, that might lead to some tractability results, is the family 𝒮 consisting of forests whose every component has at most three leaves. In this case, we exhibit the following dichotomy theorem: besides the cases that are polynomial-time solvable in general graphs, the graphs H ∈ {P₃,C₄} are the only connected ones that allow for a subexponential-time algorithm in F-free graphs for every F ∈ 𝒮 (unless the ETH fails).

Cite as

Pavel Dvořák, Tomáš Masařík, Jana Novotná, Monika Krawczyk, Paweł Rzążewski, and Aneta Żuk. List Locally Surjective Homomorphisms in Hereditary Graph Classes. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ISAAC.2022.30,
  author =	{Dvo\v{r}\'{a}k, Pavel and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana and Krawczyk, Monika and Rz\k{a}\.{z}ewski, Pawe{\l} and \.{Z}uk, Aneta},
  title =	{{List Locally Surjective Homomorphisms in Hereditary Graph Classes}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.30},
  URN =		{urn:nbn:de:0030-drops-173154},
  doi =		{10.4230/LIPIcs.ISAAC.2022.30},
  annote =	{Keywords: Homomorphism, Hereditary graphs, Subexponential-time algorithms}
}
Document
Taming Graphs with No Large Creatures and Skinny Ladders

Authors: Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ 𝒢 contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from 𝒢. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).

Cite as

Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza. Taming Graphs with No Large Creatures and Skinny Ladders. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 58:1-58:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ESA.2022.58,
  author =	{Gajarsk\'{y}, Jakub and Jaffke, Lars and Lima, Paloma T. and Novotn\'{a}, Jana and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Souza, U\'{e}verton S.},
  title =	{{Taming Graphs with No Large Creatures and Skinny Ladders}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{58:1--58:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.58},
  URN =		{urn:nbn:de:0030-drops-169969},
  doi =		{10.4230/LIPIcs.ESA.2022.58},
  annote =	{Keywords: Minimal separator, hereditary graph class}
}
Document
Track A: Algorithms, Complexity and Games
Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument

Authors: Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, and Marek Sokołowski

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw S_{t,t,t} as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time 2^𝒪(√nlog n) and a quasipolynomial-time approximation scheme with improved running time 2^𝒪(ε^{-1} log⁵ n). The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in P_t-free graphs, ensures that given an n-vertex P_t-free graph, in polynomial time we can find a set P of at most t-1 vertices, such that every connected component of G-N[P] has at most n/2 vertices. Our main technical contribution is an analog of this result for S_{t,t,t}-free graphs: given an n-vertex S_{t,t,t}-free graph, in polynomial time we can find a set P of 𝒪(t log n) vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of G-N[P] such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most n/2 vertices.

Cite as

Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, and Marek Sokołowski. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 93:1-93:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{majewski_et_al:LIPIcs.ICALP.2022.93,
  author =	{Majewski, Konrad and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana and Okrasa, Karolina and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Soko{\l}owski, Marek},
  title =	{{Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gy\'{a}rf\'{a}s' Path Argument}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{93:1--93:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.93},
  URN =		{urn:nbn:de:0030-drops-164343},
  doi =		{10.4230/LIPIcs.ICALP.2022.93},
  annote =	{Keywords: Max Independent Set, subdivided claw, QPTAS, subexponential-time algorithm}
}
Document
Faster 3-Coloring of Small-Diameter Graphs

Authors: Michał Dębski, Marta Piecyk, and Paweł Rzążewski

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
We study the 3-Coloring problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for n-vertex diameter-2 graphs this problem can be solved in subexponential time 2^{𝒪(√{n log n})}. Whether the problem can be solved in polynomial time remains a well-known open question in the area of algorithmic graphs theory. In this paper we present an algorithm that solves 3-Coloring in n-vertex diameter-2 graphs in time 2^{𝒪(n^{1/3} log² n)}. This is the first improvement upon the algorithm of Mertzios and Spirakis in the general case, i.e., without putting any further restrictions on the instance graph. In addition to standard branchings and reducing the problem to an instance of 2-Sat, the crucial building block of our algorithm is a combinatorial observation about 3-colorable diameter-2 graphs, which is proven using a probabilistic argument. As a side result, we show that 3-Coloring can be solved in time 2^{𝒪((n log n)^{2/3})} in n-vertex diameter-3 graphs. We also generalize our algorithms to the problem of finding a list homomorphism from a small-diameter graph to a cycle.

Cite as

Michał Dębski, Marta Piecyk, and Paweł Rzążewski. Faster 3-Coloring of Small-Diameter Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{debski_et_al:LIPIcs.ESA.2021.37,
  author =	{D\k{e}bski, Micha{\l} and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Faster 3-Coloring of Small-Diameter Graphs}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.37},
  URN =		{urn:nbn:de:0030-drops-146181},
  doi =		{10.4230/LIPIcs.ESA.2021.37},
  annote =	{Keywords: 3-coloring, fine-grained complexity, subexponential-time algorithm, diameter}
}
Document
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs

Authors: Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that both problems are polynomial-time solvable for sP₃-free graphs for every integer s ≥ 1; here, the graph sP₃ denotes the disjoint union of s paths on three vertices. Our results show that both problems exhibit the same behaviour on H-free graphs (subject to some open cases). This is in part explained by a new general algorithm we design for finding in a graph G a largest induced subgraph whose blocks belong to some finite class C of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs.

Cite as

Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski. Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 82:1-82:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{paesani_et_al:LIPIcs.MFCS.2021.82,
  author =	{Paesani, Giacomo and Paulusma, Dani\"{e}l and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{82:1--82:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.82},
  URN =		{urn:nbn:de:0030-drops-145224},
  doi =		{10.4230/LIPIcs.MFCS.2021.82},
  annote =	{Keywords: Feedback vertex set, even cycle transversal, odd cactus, forest, block}
}
Document
Complexity of the List Homomorphism Problem in Hereditary Graph Classes

Authors: Karolina Okrasa and Paweł Rzążewski

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). For a fixed graph H, in the list homomorphism problem, denoted by LHom(H), we are given a graph G, whose every vertex v is equipped with a list L(v) ⊆ V(H). We ask if there exists a homomorphism f from G to H, in which f(v) ∈ L(v) for every v ∈ V(G). Feder, Hell, and Huang [JGT 2003] proved that LHom(H) is polynomial time-solvable if H is a so-called bi-arc-graph, and NP-complete otherwise. We are interested in the complexity of the LHom(H) problem in F-free graphs, i.e., graphs excluding a copy of some fixed graph F as an induced subgraph. It is known that if F is connected and is not a path nor a subdivided claw, then for every non-bi-arc graph the LHom(H) problem is NP-complete and cannot be solved in subexponential time, unless the ETH fails. We consider the remaining cases for connected graphs F. If F is a path, we exhibit a full dichotomy. We define a class called predacious graphs and show that if H is not predacious, then for every fixed t the LHom(H) problem can be solved in quasi-polynomial time in P_t-free graphs. On the other hand, if H is predacious, then there exists t, such that the existence of a subexponential-time algorithm for LHom(H) in P_t-free graphs would violate the ETH. If F is a subdivided claw, we show a full dichotomy in two important cases: for H being irreflexive (i.e., with no loops), and for H being reflexive (i.e., where every vertex has a loop). Unless the ETH fails, for irreflexive H the LHom(H) problem can be solved in subexponential time in graphs excluding a fixed subdivided claw if and only if H is non-predacious and triangle-free. On the other hand, if H is reflexive, then LHom(H) cannot be solved in subexponential time whenever H is not a bi-arc graph.

Cite as

Karolina Okrasa and Paweł Rzążewski. Complexity of the List Homomorphism Problem in Hereditary Graph Classes. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{okrasa_et_al:LIPIcs.STACS.2021.54,
  author =	{Okrasa, Karolina and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Complexity of the List Homomorphism Problem in Hereditary Graph Classes}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.54},
  URN =		{urn:nbn:de:0030-drops-136990},
  doi =		{10.4230/LIPIcs.STACS.2021.54},
  annote =	{Keywords: list homomorphism, fine-grained complexity, hereditary graph classes}
}
Document
Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth

Authors: Marta Piecyk and Paweł Rzążewski

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
For graphs G,H, a homomorphism from G to H is an edge-preserving mapping from V(G) to V(H). In the list homomorphism problem, denoted by LHom(H), we are given a graph G, whose every vertex v is equipped with a list L(v) ⊆ V(H), and we need to determine whether there exists a homomorphism from G to H which additionally respects the lists L. List homomorphisms are a natural generalization of (list) colorings. Very recently Okrasa, Piecyk, and Rzążewski [ESA 2020] studied the fine-grained complexity of the problem, parameterized by the treewidth of the instance graph G. They defined a new invariant i^*(H), and proved that for every relevant graph H, i.e., such that LHom(H) is NP-hard, this invariant is the correct base of the exponent in the running time of any algorithm solving the LHom(H) problem. In this paper we continue this direction and study the complexity of the problem under different parameterizations. As the first result, we show that i^*(H) is also the right complexity base if the parameter is the size of a minimum feedback vertex set of G, denoted by fvs(G). In particular, for every relevant graph H, the LHom(H) problem - can be solved in time i^*(H)^fvs(G) ⋅ |V(G)|^𝒪(1), if a minimum feedback vertex set of G is given, - cannot be solved in time (i^*(H) - ε)^fvs(G) ⋅ |V(G)|^𝒪(1), for any ε > 0, unless the SETH fails. Then we turn our attention to a parameterization by the cutwidth ctw(G) of G. Jansen and Nederlof [TCS 2019] showed that List k-Coloring (i.e., LHom(K_k)) can be solved in time c^ctw(G) ⋅ |V(G)|^𝒪(1) for an absolute constant c, i.e., the base of the exponential function does not depend on the number of colors. Jansen asked whether this behavior extends to graph homomorphisms. As the main result of the paper, we answer the question in the negative. We define a new graph invariant mim^*(H), closely related to the size of a maximum induced matching in H, and prove that for all relevant graphs H, the LHom(H) problem cannot be solved in time (mim^*(H)-ε)^{ctw(G)}⋅ |V(G)|^𝒪(1) for any ε > 0, unless the SETH fails. In particular, this implies that, assuming the SETH, there is no constant c, such that for every odd cycle the non-list version of the problem can be solved in time c^ctw(G) ⋅ |V(G)|^𝒪(1).

Cite as

Marta Piecyk and Paweł Rzążewski. Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{piecyk_et_al:LIPIcs.STACS.2021.56,
  author =	{Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{56:1--56:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.56},
  URN =		{urn:nbn:de:0030-drops-137012},
  doi =		{10.4230/LIPIcs.STACS.2021.56},
  annote =	{Keywords: list homomorphisms, fine-grained complexity, SETH, feedback vertex set, cutwidth}
}
Document
Sparsification Lower Bounds for List H-Coloring

Authors: Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzążewski

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)


Abstract
We investigate the List H-Coloring problem, the generalization of graph coloring that asks whether an input graph G admits a homomorphism to the undirected graph H (possibly with loops), such that each vertex v ∈ V(G) is mapped to a vertex on its list L(v) ⊆ V(H). An important result by Feder, Hell, and Huang [JGT 2003] states that List H-Coloring is polynomial-time solvable if H is a so-called bi-arc graph, and NP-complete otherwise. We investigate the NP-complete cases of the problem from the perspective of polynomial-time sparsification: can an n-vertex instance be efficiently reduced to an equivalent instance of bitsize 𝒪(n^(2-ε)) for some ε > 0? We prove that if H is not a bi-arc graph, then List H-Coloring does not admit such a sparsification algorithm unless NP ⊆ coNP/poly. Our proofs combine techniques from kernelization lower bounds with a study of the structure of graphs H which are not bi-arc graphs.

Cite as

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzążewski. Sparsification Lower Bounds for List H-Coloring. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2020.58,
  author =	{Chen, Hubie and Jansen, Bart M. P. and Okrasa, Karolina and Pieterse, Astrid and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Sparsification Lower Bounds for List H-Coloring}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{58:1--58:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.58},
  URN =		{urn:nbn:de:0030-drops-134027},
  doi =		{10.4230/LIPIcs.ISAAC.2020.58},
  annote =	{Keywords: List H-Coloring, Sparsification, Constraint Satisfaction Problem}
}
Document
Finding Large H-Colorable Subgraphs in Hereditary Graph Classes

Authors: Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, and Sophie Spirkl

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


Abstract
We study the Max Partial H-Coloring problem: given a graph G, find the largest induced subgraph of G that admits a homomorphism into H, where H is a fixed pattern graph without loops. Note that when H is a complete graph on k vertices, the problem reduces to finding the largest induced k-colorable subgraph, which for k = 2 is equivalent (by complementation) to Odd Cycle Transversal. We prove that for every fixed pattern graph H without loops, Max Partial H-Coloring can be solved: - in {P₅,F}-free graphs in polynomial time, whenever F is a threshold graph; - in {P₅,bull}-free graphs in polynomial time; - in P₅-free graphs in time n^𝒪(ω(G)); - in {P₆,1-subdivided claw}-free graphs in time n^𝒪(ω(G)³). Here, n is the number of vertices of the input graph G and ω(G) is the maximum size of a clique in G. Furthermore, by combining the mentioned algorithms for P₅-free and for {P₆,1-subdivided claw}-free graphs with a simple branching procedure, we obtain subexponential-time algorithms for Max Partial H-Coloring in these classes of graphs. Finally, we show that even a restricted variant of Max Partial H-Coloring is NP-hard in the considered subclasses of P₅-free graphs, if we allow loops on H.

Cite as

Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, and Sophie Spirkl. Finding Large H-Colorable Subgraphs in Hereditary Graph Classes. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{chudnovsky_et_al:LIPIcs.ESA.2020.35,
  author =	{Chudnovsky, Maria and King, Jason and Pilipczuk, Micha{\l} and Rz\k{a}\.{z}ewski, Pawe{\l} and Spirkl, Sophie},
  title =	{{Finding Large H-Colorable Subgraphs in Hereditary Graph Classes}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.35},
  URN =		{urn:nbn:de:0030-drops-129019},
  doi =		{10.4230/LIPIcs.ESA.2020.35},
  annote =	{Keywords: homomorphisms, hereditary graph classes, odd cycle transversal}
}
Document
Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs

Authors: Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


Abstract
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). Let H be a fixed graph with possible loops. In the list homomorphism problem, denoted by LHom(H), we are given a graph G, whose every vertex v is assigned with a list L(v) of vertices of H. We ask whether there exists a homomorphism h from G to H, which respects lists L, i.e., for every v ∈ V(G) it holds that h(v) ∈ L(v). The complexity dichotomy for LHom(H) was proven by Feder, Hell, and Huang [JGT 2003]. The authors showed that the problem is polynomial-time solvable if H belongs to the class called bi-arc graphs, and for all other graphs H it is NP-complete. We are interested in the complexity of the LHom(H) problem, parameterized by the treewidth of the input graph. This problem was investigated by Egri, Marx, and Rzążewski [STACS 2018], who obtained tight complexity bounds for the special case of reflexive graphs H, i.e., if every vertex has a loop. In this paper we extend and generalize their results for all relevant graphs H, i.e., those, for which the LHom(H) problem is NP-hard. For every such H we find a constant k = k(H), such that the LHom(H) problem on instances G with n vertices and treewidth t - can be solved in time k^t ⋅ n^𝒪(1), provided that G is given along with a tree decomposition of width t, - cannot be solved in time (k-ε)^t ⋅ n^𝒪(1), for any ε > 0, unless the SETH fails. For some graphs H the value of k(H) is much smaller than the trivial upper bound, i.e., |V(H)|. Obtaining matching upper and lower bounds shows that the set of algorithmic tools that we have discovered cannot be extended in order to obtain faster algorithms for LHom(H) in bounded-treewidth graphs. Furthermore, neither the algorithm, nor the proof of the lower bound, is very specific to treewidth. We believe that they can be used for other variants of the LHom(H) problem, e.g. with different parameterizations.

Cite as

Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 74:1-74:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{okrasa_et_al:LIPIcs.ESA.2020.74,
  author =	{Okrasa, Karolina and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{74:1--74:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.74},
  URN =		{urn:nbn:de:0030-drops-129402},
  doi =		{10.4230/LIPIcs.ESA.2020.74},
  annote =	{Keywords: list homomorphisms, fine-grained complexity, SETH, treewidth}
}
Document
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs

Authors: Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, and Bartosz Walczak

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)


Abstract
Let C and D be hereditary graph classes. Consider the following problem: given a graph G in D, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C. We prove that it can be solved in 2^{o(n)} time, where n is the number of vertices of G, if the following conditions are satisfied: - the graphs in C are sparse, i.e., they have linearly many edges in terms of the number of vertices; - the graphs in D admit balanced separators of size governed by their density, e.g., O(Delta) or O(sqrt{m}), where Delta and m denote the maximum degree and the number of edges, respectively; and - the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes C and D: - a largest induced forest in a P_t-free graph can be found in 2^{O~(n^{2/3})} time, for every fixed t; and - a largest induced planar graph in a string graph can be found in 2^{O~(n^{3/4})} time.

Cite as

Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, and Bartosz Walczak. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 23:1-23:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{novotna_et_al:LIPIcs.IPEC.2019.23,
  author =	{Novotn\'{a}, Jana and Okrasa, Karolina and Pilipczuk, Micha{\l} and Rz\k{a}\.{z}ewski, Pawe{\l} and van Leeuwen, Erik Jan and Walczak, Bartosz},
  title =	{{Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{23:1--23:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.23},
  URN =		{urn:nbn:de:0030-drops-114845},
  doi =		{10.4230/LIPIcs.IPEC.2019.23},
  annote =	{Keywords: subexponential algorithm, feedback vertex set, P\underlinet-free graphs, string graphs}
}
Document
Complexity of C_k-Coloring in Hereditary Classes of Graphs

Authors: Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski, Sophie Spirkl, and Mingxian Zhong

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f:V(G) -> V(H) such that for every edge uv in E(G) it holds that f(u)f(v)in E(H). We are interested in the complexity of the problem H-Coloring, which asks for the existence of an H-coloring of an input graph G. In particular, we consider H-Coloring of F-free graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-Coloring of P_t-free graphs. We show that for every odd k >= 5 the C_k-Coloring problem, even in the precoloring-extension variant, can be solved in polynomial time in P_9-free graphs. On the other hand, we prove that the extension version of C_k-Coloring is NP-complete for F-free graphs whenever some component of F is not a subgraph of a subdivided claw.

Cite as

Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski, Sophie Spirkl, and Mingxian Zhong. Complexity of C_k-Coloring in Hereditary Classes of Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{chudnovsky_et_al:LIPIcs.ESA.2019.31,
  author =	{Chudnovsky, Maria and Huang, Shenwei and Rz\k{a}\.{z}ewski, Pawe{\l} and Spirkl, Sophie and Zhong, Mingxian},
  title =	{{Complexity of C\underlinek-Coloring in Hereditary Classes of Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.31},
  URN =		{urn:nbn:de:0030-drops-111529},
  doi =		{10.4230/LIPIcs.ESA.2019.31},
  annote =	{Keywords: homomorphism, hereditary class, computational complexity, forbidden induced subgraph}
}
  • Refine by Author
  • 16 Rzążewski, Paweł
  • 6 Okrasa, Karolina
  • 4 Novotná, Jana
  • 4 Piecyk, Marta
  • 4 Pilipczuk, Marcin
  • Show More...

  • Refine by Classification
  • 10 Theory of computation → Graph algorithms analysis
  • 7 Mathematics of computing → Graph coloring
  • 6 Mathematics of computing → Graph algorithms
  • 6 Theory of computation → Problems, reductions and completeness
  • 5 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 4 fine-grained complexity
  • 2 SETH
  • 2 W[1]-hardness
  • 2 computational complexity
  • 2 feedback vertex set
  • Show More...

  • Refine by Type
  • 21 document

  • Refine by Publication Year
  • 4 2019
  • 4 2021
  • 4 2022
  • 3 2020
  • 2 2017
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail