Karolina Okrasa

According to our database, Karolina Okrasa authored at least 24 papers between 2018 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa.

Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa, Stanislav Zivný

CoRR, July, 2025

2024

Erdös-Pósa property of tripods in directed graphs.

Marcin Brianski, Meike Hatzel, Karolina Okrasa, Michal Pilipczuk

CoRR, 2024

Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes.

Jan Goedgebeur, Jorik Jooken, Karolina Okrasa, Pawel Rzazewski, Oliver Schaudt

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

Tree Decompositions Meet Induced Matchings: Beyond Max Weight Independent Set.

Paloma T. Lima, Martin Milanic, Peter Mursic, Karolina Okrasa, Pawel Rzazewski, Kenny Storgel

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs.

Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge

Algorithmica, May, 2023

Sparsification Lower Bounds for List <i>H</i>-Coloring.

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, Pawel Rzazewski

ACM Trans. Comput. Theory, 2023

2022

On objects dual to tree-cut decompositions.

Lukasz Bozyk, Oscar Defrain, Karolina Okrasa, Michal Pilipczuk

J. Comb. Theory B, 2022

Tuza's Conjecture for Threshold Graphs.

Marthe Bonamy, Lukasz Bozyk, Andrzej Grzesik, Meike Hatzel, Tomás Masarík, Jana Novotná, Karolina Okrasa

Discret. Math. Theor. Comput. Sci., 2022

On digraphs without onion star immersions.

Lukasz Bozyk, Oscar Defrain, Karolina Okrasa, Michal Pilipczuk

CoRR, 2022

Computing List Homomorphisms in Geometric Intersection Graphs.

Sándor Kisfaludi-Bak, Karolina Okrasa, Pawel Rzazewski

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws.

Michal Debski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, Pawel Rzazewski

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

The Complexity of k-Means Clustering when Little is Known.

Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov

Proceedings of the International Conference on Machine Learning, 2022

Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument.

Konrad Majewski, Tomás Masarík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Pawel Rzazewski, Marek Sokolowski

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width.

Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill Simonov

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Complexity of the List Homomorphism Problem in Hereditary Graph Classes.

Karolina Okrasa, Pawel Rzazewski

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

2020

Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs.

Karolina Okrasa, Pawel Rzazewski

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Vertex Deletion into Bipartite Permutation Graphs.

Lukasz Bozyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, Karolina Okrasa

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

Sparsification Lower Bounds for List H-Coloring.

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, Pawel Rzazewski

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs.

Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, Manuel Sorge

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs.

Karolina Okrasa, Marta Piecyk, Pawel Rzazewski

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

H-colouring Pt-free graphs in subexponential time.

Carla Groenland, Karolina Okrasa, Pawel Rzazewski, Alex D. Scott, Paul D. Seymour, Sophie Spirkl

Discret. Appl. Math., 2019

Subexponential Algorithms for Variants of Homomorphism Problem in String Graphs.

Karolina Okrasa, Pawel Rzazewski

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

Jana Novotná, Karolina Okrasa, Michal Pilipczuk, Pawel Rzazewski, Erik Jan van Leeuwen, Bartosz Walczak

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

2018

Intersecting edge distinguishing colorings of hypergraphs.

Karolina Okrasa, Pawel Rzazewski

CoRR, 2018