Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs K Okrasa, P Rzaͅżewski
SIAM Journal on Computing 50 (2), 487-508, 2021
27 2021 H-colouring Pt-free graphs in subexponential time C Groenland, K Okrasa, P Rzążewski, A Scott, P Seymour, S Spirkl
Discrete Applied Mathematics 267, 184-189, 2019
27 2019 Subexponential algorithms for variants of the homomorphism problem in string graphs K Okrasa, P Rzążewski
Journal of Computer and System Sciences 109, 126-144, 2020
24 2020 Full complexity classification of the list homomorphism problem for bounded-treewidth graphs K Okrasa, M Piecyk, P Rzążewski
arXiv preprint arXiv:2006.11155, 2020
21 2020 The fine-grained complexity of graph homomorphism parameterized by clique-width R Ganian, T Hamm, V Korchemna, K Okrasa, K Simonov
ACM Transactions on Algorithms, 2022
13 2022 On objects dual to tree-cut decompositions Ł Bożyk, O Defrain, K Okrasa, M Pilipczuk
Journal of Combinatorial Theory, Series B 157, 401-428, 2022
10 2022 Max weight independent set in graphs with no long claws: An analog of the gyárfás’ path argument K Majewski, T Masařík, J Masaříková, K Okrasa, M Pilipczuk, P Rzążewski, ...
ACM Transactions on Computation Theory 16 (2), 1-18, 2024
9 2024 Vertex deletion into bipartite permutation graphs Ł Bożyk, J Derbisz, T Krawczyk, J Novotná, K Okrasa
Algorithmica 84 (8), 2271-2291, 2022
9 2022 Subexponential-time algorithms for finding large induced sparse subgraphs J Novotná, K Okrasa, M Pilipczuk, P Rzążewski, EJ van Leeuwen, ...
Algorithmica 83, 2634-2650, 2021
9 2021 Complexity of the list homomorphism problem in hereditary graph classes K Okrasa, P Rzążewski
arXiv preprint arXiv:2010.03393, 2020
8 2020 Sparsification Lower Bounds for List H -Coloring H Chen, BMP Jansen, K Okrasa, A Pieterse, P Rzążewski
ACM Transactions on Computation Theory 15 (3-4), 1-23, 2023
7 2023 The complexity of k-means clustering when little is known R Ganian, T Hamm, V Korchemna, K Okrasa, K Simonov
International Conference on Machine Learning, 6960-6987, 2022
5 2022 Tree decompositions meet induced matchings: beyond Max Weight Independent Set PT Lima, M Milanič, P Muršič, K Okrasa, P Rzążewski, K Štorgel
arXiv preprint arXiv:2402.15834, 2024
4 2024 Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws M Dębski, Z Lonc, K Okrasa, M Piecyk, P Rzążewski
arXiv preprint arXiv:2205.13270, 2022
4 2022 Tuza's Conjecture for Threshold Graphs M Bonamy, Ł Bożyk, A Grzesik, M Hatzel, T Masařík, J Novotná, K Okrasa
Discrete Mathematics & Theoretical Computer Science 24 (Graph Theory), 2022
3 2022 Computing list homomorphisms in geometric intersection graphs S Kisfaludi-Bak, K Okrasa, P Rzążewski
International Workshop on Graph-Theoretic Concepts in Computer Science, 313-327, 2022
2 2022 The complexity of routing problems in forbidden-transition graphs and edge-colored graphs T Bellitto, S Li, K Okrasa, M Pilipczuk, M Sorge
Algorithmica 85 (5), 1202-1250, 2023
1 2023 On digraphs without onion star immersions Ł Bożyk, O Defrain, K Okrasa, M Pilipczuk
arXiv preprint arXiv:2211.15477, 2022
1 2022 The complexity of connectivity problems in forbidden-transition graphs and edge-colored graphs T Bellitto, S Li, K Okrasa, M Pilipczuk, M Sorge
arXiv preprint arXiv:2009.12892, 2020
1 2020 Minimal obstructions to -coloring in hereditary graph classes J Goedgebeur, J Jooken, K Okrasa, P Rzążewski, O Schaudt
arXiv preprint arXiv:2404.11704, 2024
2024