Projekty finansowane przez NCN


Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Program optymalności w problemach homomorfizmu grafów

2018/31/D/ST6/00062

Słowa kluczowe:

homomorfizm grafów złożoność obliczeniowa algorytmy

Deskryptory:

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
  • ST1_14: Kombinatoryka

Panel:

ST6 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Politechnika Warszawska, Wydział Matematyki i Nauk Informacyjnych

woj. mazowieckie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

dr Paweł Rzążewski 

Liczba wykonawców projektu: 4

Konkurs: SONATA 14 - ogłoszony 2018-09-14

Przyznana kwota: 306 680 PLN

Rozpoczęcie projektu: 2019-06-13

Zakończenie projektu: 2023-06-12

Planowany czas trwania projektu: 48 miesięcy (z wniosku)

Status projektu: Projekt rozliczony

Opis Projektu

Pobierz opis projektu w formacie .pdf

Uwaga - opisy projektów zostały sporządzone przez samych autorów wniosków i w niezmienionej formie umieszczone w systemie.

Zakupiona aparatura

  1. Laptop. Za kwotę 7 500 PLN

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (14)
  • Teksty w publikacjach pokonferencyjnych (22)
  1. Clique‐width: Harnessing the power of atoms
    Autorzy:
    Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Paweł Rzążewski
    Czasopismo:
    Journal of Graph Theory (rok: 2023, tom: (online), strony: n/a), Wydawca: Wiley
    Status:
    Opublikowana
    Doi:
    10.1002/jgt.23000 - link do publikacji
  2. Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
    Autorzy:
    Jacob Focke, Daniel Marx, Paweł Rzążewski
    Czasopismo:
    ACM Transactions on Algorithms (rok: 2023, tom: online, strony: b/d), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3640814 - link do publikacji
  3. Faster 3-coloring of small-diameter graphs
    Autorzy:
    Michał Dębski, Marta Piecyk, Paweł Rzążewski
    Czasopismo:
    SIAM Journal on Discrete Mathematics (rok: 2022, tom: 36, strony: 2205-2224), Wydawca: SIAM
    Status:
    Opublikowana
    Doi:
    10.1137/21M1447714 - link do publikacji
  4. Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
    Autorzy:
    Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzaͅżewski, Sophie Spirkl
    Czasopismo:
    SIAM Journal on Discrete Mathematics (rok: 2021, tom: 35, strony: 2357-2386), Wydawca: SIAM
    Status:
    Opublikowana
    Doi:
    10.1137/20M1367660 - link do publikacji
  5. Complexity of Ck-coloring in hereditary classes of graphs
    Autorzy:
    Maria Chudnovsky, Shenwei Huang, Paweł Rzążewski, Sophie Spirkl, Mingxian Zhong
    Czasopismo:
    Information and Computation (rok: 2023, tom: 292, strony: 105015), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.ic.2023.105015 - link do publikacji
  6. Feedback Vertex Set and Even Cycle Transversal for H -Free Graphs: Finding Large Block Graphs
    Autorzy:
    Giacomo Paesani, Daniel Paulusma, Paweł Rzążewski
    Czasopismo:
    SIAM Journal on Discrete Mathematics (rok: 2022, tom: 36, strony: 2453-2472), Wydawca: SIAM
    Status:
    Opublikowana
    Doi:
    10.1137/22M1468864 - link do publikacji
  7. On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
    Autorzy:
    Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Paweł Rzążewski
    Czasopismo:
    Algorithmica (rok: 2020, tom: 82, strony: 2841–2866), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-020-00706-6 - link do publikacji
  8. Sparsification Lower Bounds for List H-Coloring
    Autorzy:
    Hubie Chen, Bart M.P. Jansen, Karolina Okrasa, Astrid Pieterse, Paweł Rzążewski
    Czasopismo:
    ACM Transactions on Computation Theory (rok: 2023, tom: 15, strony: 45314), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3612938 - link do publikacji
  9. Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
    Autorzy:
    Karolina Okrasa, Paweł Rzaͅżewski
    Czasopismo:
    SIAM Journal on Computing (rok: 2021, tom: 50, strony: 487-508), Wydawca: SIAM
    Status:
    Opublikowana
    Doi:
    10.1137/20M1320146 - link do publikacji
  10. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument
    Autorzy:
    Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski
    Czasopismo:
    ACM Transactions on Computation Theory (rok: 2023, tom: online, strony: b/d), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3636422 - link do publikacji
  11. Towards the Chen-Raspaud conjecture
    Autorzy:
    Katarzyna Łyczek, Maria Nazarczuk, Paweł Rzążewski
    Czasopismo:
    Discrete Mathematics (rok: 2024, tom: 347, strony: n/a), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.disc.2023.113798 - link do publikacji
  12. Subexponential algorithms for variants of homomorphism problem in string graphs
    Autorzy:
    Karolina Okrasa, Paweł Rzążewski
    Czasopismo:
    Journal of Computer and System Sciences (rok: 2020, tom: 109, strony: 126-144), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.jcss.2019.12.004 - link do publikacji
  13. List covering of regular multigraphs with semi-edges
    Autorzy:
    Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, Paweł Rzążewski
    Czasopismo:
    Algorithmica (rok: 2023, tom: online, strony: b/d), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-023-01163-7 - link do publikacji
  14. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs
    Autorzy:
    Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
    Czasopismo:
    Algorithmica (rok: 2020, tom: n/a, strony: n/a), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-020-00745-z - link do publikacji
  1. Computing list homomorphisms in geometric intersection graphs
    Autorzy:
    Sandor Kisfaludi-Bak, Karolina Okrasa, Paweł Rzążewski,
    Konferencja:
    International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022) (rok: 2022, ), Wydawca: Springer
    Data:
    konferencja 22-24.06.2022
    Status:
    Opublikowana
  2. Faster 3-Coloring of Small-Diameter Graphs
    Autorzy:
    Michał Dębski, Marta Piecyk, Paweł Rzążewski
    Konferencja:
    European Symposium on Algorithms (ESA 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.09.6-8
    Status:
    Opublikowana
  3. Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs
    Autorzy:
    Karolina Okrasa, Marta Piecyk, Paweł Rzążewski
    Konferencja:
    28th Annual European Symposium on Algorithms (ESA 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 7-9.09.2020
    Status:
    Opublikowana
  4. Induced subgraphs of bounded treewidth and the container method
    Autorzy:
    Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, Paul Seymour
    Konferencja:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) (rok: 2021, ), Wydawca: SIAM
    Data:
    konferencja 2021.01.10-13
    Status:
    Opublikowana
  5. Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument
    Autorzy:
    Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski
    Konferencja:
    49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) (rok: 2022, ), Wydawca: LIPIcs
    Data:
    konferencja 4-8.07.2022
    Status:
    Opublikowana
  6. Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
    Autorzy:
    Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Paweł Rzążewski
    Konferencja:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2022) (rok: 2022, ), Wydawca: SIAM
    Data:
    konferencja 9-12.01.2022
    Status:
    Opublikowana
  7. Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
    Autorzy:
    Giacomo Paesani, Daniel Paulusma, Paweł Rzążewski
    Konferencja:
    International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.08.23-27
    Status:
    Opublikowana
  8. Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
    Autorzy:
    Karolina Okrasa, Paweł Rzążewski
    Konferencja:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2020) (rok: 2020, ), Wydawca: SIAM
    Data:
    konferencja 5-8.01.2020
    Status:
    Opublikowana
  9. Sparsification Lower Bounds for List H-Coloring
    Autorzy:
    Hubie chen, Bart M.P. Jansen, Karolina Okrasa, Astrid Pieterse, Paweł Rzążewski
    Konferencja:
    31st International Symposium on Algorithms and Computation (ISAAC 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 14-18.12.2020
    Status:
    Opublikowana
  10. Clique-Width: Harnessing the Power of Atoms
    Autorzy:
    Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Paweł Rzążewski
    Konferencja:
    WG 2020: Graph-Theoretic Concepts in Computer Science (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 24-26.06.2020
    Status:
    Opublikowana
  11. Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
    Autorzy:
    Jacob Focke, Daniel Marx, Paweł Rzążewski
    Konferencja:
    ACM-SIAM Symposium on Discrete Algorithms (SODA 2022) (rok: 2022, ), Wydawca: SIAM
    Data:
    konferencja 9-12.01.2022
    Status:
    Opublikowana
  12. Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
    Autorzy:
    Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzążewski, Sophie Spirkl
    Konferencja:
    28th Annual European Symposium on Algorithms (ESA 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 7-9.09.2020
    Status:
    Opublikowana
  13. List Covering of Regular Multigraphs
    Autorzy:
    Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, Paweł Rzążewski
    Konferencja:
    International Workshop on Combinatorial Algorithms (IWOCA 2022) (rok: 2022, ), Wydawca: Springer
    Data:
    konferencja 7-9.06.2022
    Status:
    Opublikowana
  14. Quasi-polynomial-time algorithm for Independent Set in Pt-free graphs via shrinking the space of induced paths
    Autorzy:
    Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
    Konferencja:
    Symposium on Simplicity in Algorithms (SOSA 2021) (rok: 2021, ), Wydawca: SIAM
    Data:
    konferencja 2021.01.11-12
    Status:
    Opublikowana
  15. Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs
    Autorzy:
    Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak
    Konferencja:
    14th International Symposium on Parameterized and Exact Computation (IPEC 2019) (rok: 2019, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-13.09.2019
    Status:
    Opublikowana
  16. Classifying Subset Feedback Vertex Set for H-Free Graphs
    Autorzy:
    Giacomo Paesani, Daniel Paulusma, Paweł Rzążewski
    Konferencja:
    International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022) (rok: 2022, ), Wydawca: Springer
    Data:
    konferencja 22-24.06.2022
    Status:
    Opublikowana
  17. Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws
    Autorzy:
    Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, Paweł Rzążewski
    Konferencja:
    33rd International Symposium on Algorithms and Computation (ISAAC 2022) (rok: 2022, ), Wydawca: LIPIcs
    Data:
    konferencja 19-21.12.2022
    Status:
    Opublikowana
  18. Finding large induced sparse subgraphs in C_{>t} -free graphs in quasipolynomial time
    Autorzy:
    Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski
    Konferencja:
    Symposium on Theory of Computing (STOC 2021) (rok: 2021, ), Wydawca: ACM
    Data:
    konferencja 2021.06.21-25
    Status:
    Opublikowana
  19. Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth
    Autorzy:
    Maria Piecyk, Paweł Rzążewski
    Konferencja:
    International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.03.16-19
    Status:
    Opublikowana
  20. Complexity of the List Homomorphism Problem in Hereditary Graph Classes
    Autorzy:
    Karolina Okrasa, Paweł Rzążewski
    Konferencja:
    International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (rok: 2021, ), Wydawca: LIPIcs
    Data:
    konferencja 2021.03.16-19
    Status:
    Opublikowana
  21. List Locally Surjective Homomorphisms in Hereditary Graph Classes
    Autorzy:
    Pavel Dvořák, Monika Krawczyk, Tomáš Masařík, Jana Novotná, Paweł Rzążewski, Aneta Żuk
    Konferencja:
    33rd International Symposium on Algorithms and Computation (ISAAC 2022) (rok: 2022, ), Wydawca: LIPIcs
    Data:
    konferencja 19-21.12.2022
    Status:
    Opublikowana
  22. Parameterized Inapproximability of Independent Set in H-Free Graphs
    Autorzy:
    Pavel Dvořák, Andreas Emil Feldmann, Ashutosh Rai, Paweł Rzążewski
    Konferencja:
    WG 2020: Graph-Theoretic Concepts in Computer Science (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 24-26.06.2020
    Status:
    Opublikowana