13 citations · 77 across the 56 of their papers we have counts for
21 papers · 1 filter
Parameterized complexity of -Coloring in graphs with no long induced paths
Paweł Rzążewski
We study the parameterized complexity of (List) -Coloring in -free graphs, where is a linear forest, that is, a disjoint union of paths. First, considering as the par…
Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
Paweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski
The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, ther…
Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
Daniel Lokshtanov, Michał Pilipczuk, Paweł Rzążewski
The independence number of a tree decomposition is the size of a largest independent set contained in a single bag. The tree-independence number of a graph is the minimum indep…
Sparse induced subgraphs in -free graphs of bounded clique number
Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk +2
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 larges…
Tree decompositions meet induced matchings: beyond Max Weight Independent Set
Paloma T. Lima, Martin Milanič, Peter Muršič +3
For a tree decomposition of a graph , by we denote the size of a largest induced matching in all of whose edges intersect one bag of $\mathcal…
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland, Daniel Lokshtanov, Tomáš Masařík +3
We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on -free graphs (graphs excluding a fixed graph as an induced subgraph)…
Tree decompositions with bounded independence number: beyond independent sets
Martin Milanič, Paweł Rzążewski
We continue the study of graph classes in which the treewidth can only be large due to the presence of a large clique, and, more specifically, of graph classes with bounded tree-in…
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
Konrad Majewski, Tomáš Masařík, Jana Novotná +4
We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw as an induced subgraph [Chudnovsky, Pilipczuk, Pilip…
List Locally Surjective Homomorphisms in Hereditary Graph Classes
Pavel Dvořák, Monika Krawczyk, Tomáš Masařík +3
A locally surjective homomorphism from a graph to a graph is an edge-preserving mapping from to that is surjective in the neighborhood of each vertex in .…
Computing list homomorphisms in geometric intersection graphs
Sándor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzążewski
A homomorphism from a graph to a graph is an edge-preserving mapping from to . Let be a fixed graph with possible loops. In the list homomorphism problem,…
Classifying Subset Feedback Vertex Set for -Free Graphs
Giacomo Paesani, Daniël Paulusma, Paweł Rzążewski
In the Feedback Vertex Set problem, we aim to find a small set of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires to intersect…
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet +6
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Cliq…
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
Giacomo Paesani, Daniël Paulusma, Paweł Rzążewski
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on -free graphs, that is, graphs that do not contain some fixed graph as an induced subgra…
Faster 3-coloring of small-diameter graphs
Michał Dębski, Marta Piecyk, Paweł Rzążewski
We study the 3-\textsc{Coloring} problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for -vertex diameter-2 graphs this problem can be solved in su…
Quasi-polynomial-time algorithm for Independent Set in -free graphs via shrinking the space of induced paths
Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in -free graphs, that is, graphs…
Complexity of -coloring in hereditary classes of graphs
Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski +2
For a graph , a graph is \emph{-free} if it does not contain an induced subgraph isomorphic to . For two graphs and , an \emph{-coloring} of is a mapping…
Finding large -colorable subgraphs in hereditary graph classes
Maria Chudnovsky, Jason King, Michał Pilipczuk +2
We study the \textsc{Max Partial -Coloring} problem: given a graph , find the largest induced subgraph of that admits a homomorphism into , where is a fixed patter…
Induced subgraphs of bounded treewidth and the container method
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk +2
A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By we denote a path on vertices. In this paper we give polynomial-…
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson +3
A graph is -free if it contains no induced subgraph isomorphic to . We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and O…
Finding small-width connected path decompositions in polynomial time
Dariusz Dereniowski, Dorota Osula, Paweł Rzążewski
A connected path decomposition of a simple graph is a path decomposition such that the subgraph of induced by is connected for ea…
Designing RNA Secondary Structures is Hard
Édouard Bonnet, Paweł Rzążewski, Florian Sikora
An RNA sequence is a word over an alphabet on four elements called bases. RNA sequences fold into secondary structures where some bases match one another while others…