Karolina Okrasa

Most-cited papers

Tree decompositions meet induced matchings: beyond Max Weight Independent Set
P. T. de Lima, Martin Milanič, Peter Muršič, Karolina Okrasa +2 more
2024Embedded Systems and Applications34 citations
Semantic Scholar
H-colouring Pt-free graphs in subexponential time
Carla Groenland, Karolina Okrasa, Paweł Rzaͅżewski, A. Scott +2 more
2018Discrete Applied Mathematics30 citations Open access
Semantic Scholar
Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
Karolina Okrasa, Paweł Rzaͅżewski
2020ACM-SIAM Symposium on Discrete Algorithms27 citations Open access
Semantic Scholar
Subexponential algorithms for variants of the homomorphism problem in string graphs
Karolina Okrasa, Paweł Rzaͅżewski
2020Journal of computer and system sciences (Print)21 citations Open access
Semantic Scholar
Full complexity classification of the list homomorphism problem for bounded-treewidth graphs
Karolina Okrasa, Marta Piecyk, Paweł Rzaͅżewski
2020Embedded Systems and Applications20 citations
Semantic Scholar
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa +1 more
2022International Colloquium on Automata, Languages and Programming18 citations Open access
Semantic Scholar
Subexponential algorithms for variants of homomorphism problem in string graphs
Karolina Okrasa, Paweł Rzaͅżewski
2018International Workshop on Graph-Theoretic Concepts in Computer Science18 citations Open access
Semantic Scholar
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs
Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzaͅżewski +2 more
2019Algorithmica16 citations Open access
Semantic Scholar
The Complexity of k-Means Clustering when Little is Known
Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa +1 more
2022International Conference on Machine Learning10 citations
Semantic Scholar
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 Masaříková, Karolina Okrasa +3 more
2022International Colloquium on Automata, Languages and Programming9 citations
Semantic Scholar
Minimal obstructions to C5-coloring in hereditary graph classes
J. Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzaͅżewski +1 more
2024Information and Computation8 citations Open access
Semantic Scholar
Complexity of the list homomorphism problem in hereditary graph classes
Karolina Okrasa, Paweł Rzaͅżewski
2020arXiv.org8 citations
Semantic Scholar
Tuza's Conjecture for Threshold Graphs
Marthe Bonamy, Łukasz Bożyk, Andrzej Grzesik, Meike Hatzel +3 more
2021Discrete Mathematics & Theoretical Computer Science7 citations Open access
Semantic Scholar
The Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
Thomas Bellitto, Shaohua Li, Karolina Okrasa, M. Pilipczuk +1 more
2022Algorithmica6 citations Open access
Semantic Scholar
On objects dual to tree-cut decompositions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa, Michał Pilipczuk
2021J. Comb. Theory B6 citations Open access
Semantic Scholar
Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
Karolina Okrasa, Paweł Rzaͅżewski
2021SIAM journal on computing (Print)6 citations Open access
Semantic Scholar
Vertex Deletion into Bipartite Permutation Graphs
Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotn'a +1 more
2020Algorithmica5 citations Open access
Semantic Scholar
Sparsification Lower Bounds for List H-Coloring
Hubie Chen, B. Jansen, Karolina Okrasa, A. Pieterse +1 more
2020International Symposium on Algorithms and Computation4 citations Open access
Semantic Scholar
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa, Stanislav Živný
2025IEEE Annual Symposium on Foundations of Computer Science3 citations Open access
Semantic Scholar
Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws
M. Debski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk +1 more
2022International Symposium on Algorithms and Computation3 citations Open access
Semantic Scholar
Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes
J. Goedgebeur, Jorik Jooken, Karolina Okrasa, Paweł Rzaͅżewski +1 more
2024International Symposium on Mathematical Foundations of Computer Science2 citations
Semantic Scholar
Computing list homomorphisms in geometric intersection graphs
Sándor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzaͅżewski
2022International Workshop on Graph-Theoretic Concepts in Computer Science2 citations Open access
Semantic Scholar
Complexity of the List Homomorphism Problem in Hereditary Graph Classes
Karolina Okrasa, Paweł Rzaͅżewski
2020Symposium on Theoretical Aspects of Computer Science2 citations Open access
Semantic Scholar
On digraphs without onion star immersions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa, Michał Pilipczuk
2022J. Comb. Theory B1 citations Open access
Semantic Scholar
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
Thomas Bellitto, Shaohua Li, Karolina Okrasa, M. Pilipczuk +1 more
2020International Symposium on Algorithms and Computation1 citations
Semantic Scholar
Potatoes and Onions
Marcin Briański, Meike Hatzel, Karolina Okrasa, Michał Pilipczuk
20260 citations
Semantic Scholar
Erdös-Pósa property of tripods in directed graphs
Marcin Briański, Meike Hatzel, Karolina Okrasa, Michał Pilipczuk
2024arXiv.org0 citations
Semantic Scholar
D M ] 2 2 M ar 2 01 9 H-colouring P t-free graphs in subexponential time
Carla Groenland, Karolina Okrasa, Paweł Rzaͅżewski, A. Scott +3 more
20190 citations
Semantic Scholar
Intersecting edge distinguishing colorings of hypergraphs
Karolina Okrasa, Paweł Rzaͅżewski
2018arXiv.org0 citations
Semantic Scholar